#64. KMP 字符串匹配
KMP 字符串匹配
Description
给出两个字符串 和 ,若 的区间 子串与 完全相同,则称 在 中出现了,其出现位置为 。 现在请你求出 在 中所有出现的位置。
定义一个字符串 的 为 的一个非 本身的子串,满足 既是的前缀,又是 的后缀。 对于 ,你还需要求出对于其每个前缀 的最长 的长度。
Format
Input
第一行为一个字符串,即为 。 第二行为一个字符串,即为 。.
Output
首先输出若干行,每行一个整数,按从小到大的顺序输出 在 中出现的位置。 最后一行输出 个整数,第 个整数表示 的长度为的前缀的最长 长度。
Samples
ABABABC
ABA
1
3
0 0 1