给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。
输出格式
共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。
数据范围
1≤N≤10^5
1≤M≤10^6
输入样例：
3
aba
5
ababa
输出样例：
0 2
暴力解法 时间复杂度平方级别会超时
1. int i,j; 2. for(i=1;i<=m-n+1;i++){ 3. for(j=1;j<=n;j++){ 4. if(s[i]!=s[j]) break; 5. } 6. if(j>m) cout<<i<<" "; 7. }
KMP算法
1.取最长的相等前后缀，可以保证不漏解。
2.通过模式串前后缀的自我匹配的长度，计算next函数，给指针打一张表，失配时就跳到next[j]的位置继续匹配。
next函数
next[i]表示模式串P[1，i]中相等前后缀的最长长度。
next函数
next[i]表示模式串P[1，i]中相等前后缀的最长长度。
双指针：i扫描模式串，j扫描前缀。
初始化，ne[1]=0，i=2，j=0。
每轮for循环，i向右走一步。
1.若P[i]！=P[j+1]，让j回跳到能匹配的位置，如果找不到能匹配的位置，j回跳到0。
2.若P[i]==P[j+1]，让j+1，指向匹配前缀的末尾。
3.next[i]等于j的值。
1. int ne[N];//最长相等真前后缀的长度 2. void do_next() { 3. ne[1]=0;//初始化数据 4. for(int i=2,j=0;i<=n;i++){//i扫描字符串 j扫描前缀 5. while(j && p[i]!=p[j+1]) j=ne[j];//回跳 6. if(p[i]==p[j+1]) j++;//相同 增加一个 7. ne[i]=j;//记录P[1，i]中相等前后缀的最长长度 8. } 9. }
j指针所走的总步数就决定了总的执行次数。
每轮for，j至多+1，那么j一共向右至多走n步，往左跳的步数加起来不会超过n步，否则j变为负数，故j的总步数不会超过2n。例a…ab。所以时间复杂度O(n)。
模式串与主串匹配
双指针：i扫描主串，j扫描模式串。
初始化，i=1，j=0。每轮for，i向右走一步。
1.若S[i]！=P[j+1]，让j回跳到能匹配的位置，如果找不到能匹配的位置，j回跳到0。
2.若S[i]==P[j+1]，让j向右走一步。
3.若匹配成功，输出匹配位置。
1. void do_KMP(){ 2. for(int i=1,j=0;i<=m;i++){ 3. while(j &&s[i]!=p[j+1]) j=ne[j]; //不同 j指针回跳 4. if(s[i]==p[j+1]) j++; //相同 j指针右移 5. if(j==n) printf("%d ",i-n+1);//匹配成功 输出位置 6. } 7. }
j指针所走的总步数就决定了总的执行次数。
每轮for，j至多+1，那么j一共向右至多走m步，往左跳的步数加起来不会超过m步，否则j变为负数，故j最多走2m步。例a……a，ab。所以时间复杂度0(m)。
1. //完整参考代码 2. #include <iostream> 3. #include <cstdio> 4. #include <cstring> 5. using namespace std; 6. const int N=1e6+5; 7. int m,n; 8. char s[N],p[N]; 9. int ne[N];//最长相等的真前后缀的长度 10. void do_next(){ 11. ne[1]=0; 12. for(int i=2,j=0;i<=n;i++){ 13. while(j&&p[i]!=p[j+1])j=ne[j]; 14. if(p[i]==p[j+1]) j++; 15. ne[i]=j; 16. } 17. } 18. void do_KMP(){ 19. for(int i=1,j=0;i<=m;i++){ 20. while(j &&s[i]!=p[j+1]) j=ne[j]; 21. if(s[i]==p[j+1]) j++; 22. if(j==n) printf("%d ",i-n);//注意题目当中的下标起点是0还是1 23. } 24. } 25. int main() 26. { 27. cin>>n; 28. cin>>p+1; 29. cin>>m; 30. cin>>s+1; 31. do_next(); 32. do_KMP(); 33. return 0; 34. }
