假设主串：S: S[1] S[2] S[3] ……S[n]
模式串：T: T[1] T[2] T[3]…..T[m]
现在我们假设主串第i 个字符与模式串的第j(j<=m)个字符‘失配’后，主串第i 个字符与模式串的第k(k<j)个字符继续比较,此时就有S[i] != T[j]
主串: S[1]...S[i-j+1]...S[i-1]S[i]...
||(匹配) || ≠
模式串: T[1]... T[j-1] T[j]
由此，可以得到关系式如下
T[1]T[2]T[3]...T[j-1] = S[i-j+1]...S[i-1]
由于S[i] != T[j],接下来S[i]将与T[k]继续比较，则模式串中的前k-1咯字符串必须满足下列关系式，并且不可能存在k'>k满足下列关系式:
T[1]T[2]T[3]...T[k-1] = S[j-k+1]S[j-k+2]...S[i-1] (k<j)
也就是说：
主串： S[1]...S[i-k+1]S[i-k+2]...S[i-1]S[i]...
|| || || ?(待比较)
模式串： T[1] T[2]... T[k-1] T[k]
现在可以把前面的关系综合总结如下
S[1]...S[i-j+1]...S[i-k+1]S[i-k+2]...S[i-1]S[i]...
|| || || || ≠
T[1]... T[j-k+1] T[j-k+2]... T[j-1] T[j]
|| || || ?
T[1] T[2] ... T[k-1] T[k]
现在唯一的任务就是如何求k了，通过一个next函数求。
/* pku3461(Oulipo), hdu1711(Number Sequence) 这个模板 字符串是从0开始的 Next数组是从1开始的 */ #include <iostream> #include <cstring> using namespace std; const int N = 1000002; int next[N]; char S[N], T[N]; int slen, tlen; void getNext() { int j, k; j = 0; k = -1; next[0] = -1; while(j < tlen) if(k == -1 || T[j] == T[k]) next[++j] = ++k; else k = next[k]; } /* 返回模式串T在主串S中首次出现的位置 返回的位置是从0开始的。 */ int KMP_Index() { int i = 0, j = 0; getNext(); while(i < slen && j < tlen) { if(j == -1 || S[i] == T[j]) { i++; j++; } else j = next[j]; } if(j == tlen) return i - tlen; else return -1; } /* 返回模式串在主串S中出现的次数 */ int KMP_Count() { int ans = 0; int i, j = 0; if(slen == 1 && tlen == 1) { if(S[0] == T[0]) return 1; else return 0; } getNext(); for(i = 0; i < slen; i++) { while(j > 0 && S[i] != T[j]) j = next[j]; if(S[i] == T[j]) j++; if(j == tlen) { ans++; j = next[j]; } } return ans; } int main() { int TT; int i, cc; cin>>TT; while(TT--) { cin>>S>>T; slen = strlen(S); tlen = strlen(T); cout<<"模式串T在主串S中首次出现的位置是: "<<KMP_Index()<<endl; cout<<"模式串T在主串S中出现的次数为: "<<KMP_Count()<<endl; } return 0; } /* test case aaaaaa a abcd d aabaa b */