整理了一下KMP的写法:
这个是我自己写的(个人推导,可能在时间复杂度上表现较弱,但是非常帮助初学者进行理解!)
下面是代码, ne 是next数组。我这个next数组表示的是:
ne[i] : 当s[i]和target不匹配的时候,可以向前移动几格
例如
s : abc abc x
target : abc abe abc abc x
当s去匹配target的时候,匹配导了target[6] : e的时候,匹配失败了,那我们不需要仅仅向前移动一格,可以直接移到target[4] 处进行再匹配。
abc abe abc abc x ---> abc abe abc abc x
↑ ↑
abc abc x abc abc x
那么ne[6] = 3表示前进3.
下面先有暴力做法,再给出相对正确做法。
ne[1] = 1;// for (int i = 1; i < n; i ++ ){// //当i位置不匹配的时候,考虑s.substr(0,i);// //即求出最长前缀和最长后缀的相同情况下的长度// int cur = i;// for (int j = 1; j <= i; j ++ ){// bool f = false;// for (int k = j; k <= i; k ++ ){// if(s[k] != s[k - j]){f = true ; break;}// }// if(!f){cur = j ; break;}// }// ne[i] = cur;// printf("%d\n" , cur);// }for (int i = 2; i <= n; i ++ ){if(s[i] == s[1]){int p = 1;ne[i] = ne[i-1];while(s[i + p] == s[1 + p]){ne[i + p] = ne[i + p - 1];p++;}i += (p - 1);}else{ne[i] = i;}}
最优代码:
#include <iostream>using namespace std;const int N = 100010, M = 1000010;int n, m;
int ne[N];
char s[M], p[N];int main()
{cin >> n >> p + 1 >> m >> s + 1;for (int i = 2, j = 0; i <= n; i ++ ){while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j ++ ;ne[i] = j;}for (int i = 1, j = 0; i <= m; i ++ ){while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++ ;if (j == n){printf("%d ", i - n);j = ne[j];}}return 0;
}