给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串 P 在模式串 S 中多次作为子串出现。
求出模板串 P 在模式串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。
输出格式
共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。
数据范围
1≤N≤105
1≤M≤106
输入样例：
3 aba 5 ababa
输出样例：
0 2
代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
reader.nextLine();
String P = reader.nextLine();
// 模板串
char p[] = new char[n + 1];
// n 是模板串的长度 储存的数组比原串的长度大1
for (int i = 1; i <= n; i++) {
p[i] = P.charAt(i - 1);
// 因为数组是存的与之前的原先的大串对比是错1位的
}
int m = reader.nextInt();
reader.nextLine();
String S = reader.nextLine();
// 总串
char s[] = new char[m + 1];
for (int i = 1; i <= m; i++) {
s[i] = S.charAt(i - 1);
}
// 构造前缀数组
int next[] = new int[n + 1];
for (int i = 2, j = 0; i <= n; i++) {
// i从2开始,因为next[1]肯定为 0
// 意思是当模板串长度为1的时候 他的前缀一定无法与后缀匹配 也就是前缀长度是0,与自身匹配无效,所以是从2开始的
while (j != 0 && p[i] != p[j + 1])
//j不等于 0
j = next[j];
if (p[i] == p[j + 1])
j++;
next[i] = j;
}
// kmp 匹配
for (int i = 1, j = 0; i <= m; i++) {
while (j != 0 && s[i] != p[j + 1]) {
j = next[j];// s[i]与p[j+1]不匹配
}
if (s[i] == p[j + 1]) {
j++;// 匹配时将j++进行下一个字符得匹配
}
if (j == n) {
// 匹配了n字符了 代表整个模板串完全匹配成功了
System.out.print(i - n + " ");
j = next[j];
// 匹配成功后继续搜索
}
}
}
}
