给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。
输入格式
第一行输入整数N，表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M，表示字符串S的长度。
第四行输入字符串M。
输出格式
共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。
数据范围
1≤N≤104
1≤M≤105
输入样例
3
aba
5ababa
KMP算法求字符串匹配。文本串为S，匹配串为P，不难想到暴力做法，即从S和P的第一个字符开始，逐一比对，如果二者相同，那么S和P都前进到下一个字符，如果不相同，那么S回退到第一个字符之后的一个字符，作为新的比对起点，而P回退到第一个字符。
KMP算法的思想在于，同样是逐一比对，但当遇到不相同字符时，S串的指针不回退，而P串的指针不必回退到第一个字符，而是j = next[j]（假设j是模式串P的指针）。
举例：
文本串S：...REGRET...
匹配串P: REGROW
这里E和O不匹配，保持文本串S的指针i不变，将匹配串指针j移动到next[j]
文本串S：...REGRET...
匹配串P: REGROW
所以next[]数组的意义就是利用匹配串自身的信息--找到最长的相同的前缀和后缀，类似上面的示例，就可以将j移动到一个合适的位置，让P的后缀匹配到的S的内容用P的前缀来匹配。
那么next[i]怎么求呢？假设我们已经知道next[j]，递推next[j+1]，如果next[j] = t，即在P[0, j)中，最大长度的真前缀和真后缀的匹配长度为t，如果P[j] = P[t],那很好，直接将这相同的二位分别加入真前缀和真后缀之中，那么整个P[0, j+1)的模式串的匹配长度就变为t+1。如果P[j]!=P[t]，那么我们就继续缩小相同前后缀的范围，即看next[t]，这代表了在P[0, next[t])长度内真前后缀的长度，再和P[j]比较，这一过程一直持续，知道找到了P[j]=P[t]，或者t=-1时结束。
代码
//求next[]数组
void get_next(int length){
int t = Next[0] = -1;
for(int j = 0; j < length-1; ){
if(t < 0 || P[j] == P[t]){ t++; j++; Next[j] = t;}
else
t = Next[t];
}
}
//
int main(){
int n, m;
scanf("%d", &n);
scanf("%s", P);
scanf("%d", &m);
scanf("%s", S);
get_next(n);
int i = 0, j = 0;
while(j < m ){ //i指向匹配串，j指向文本串
if(i < 0 || S[j] == P[i]) { i++; j++;}
else i = Next[i];
if(i == n){ printf("%d ", j-i); i = Next[i-1]; --j;}
}
}