KMP-suanfa.rar_kmp string

#include <iostream> using std::cin; using std::cout; using std::endl; #define tlength 5 #define slength 13 char *T="abcac"; char *S = "ababcabcacbab"; int next[tlength]; void GetNext() { int j = 1,k; next[0] = -1; k = -1; while(T[j] != '\0') { if (k == -1 || T[j-1] == T[k]) { next[j] = k + 1; k = next[j]; j++; } else k = next[next[j-1]]; } // for (j = 0;j < tlength;++j) // { // cout<<next[j]<<endl; // } } void Compare() { int i,j = 0; bool has = false; for (i = 0;i < slength - tlength + 1;++i) { while(j != -1 && j < tlength) { if (T[j] == S[i]) { i++; j++; if (j == tlength) { cout<<"匹配字符位置为"<<i-1<<endl; has = true; } } else j = next[j]; } j++; } if (!has) { cout<<"无匹配字符"<<endl; } } int main() { GetNext(); Compare(); // cout<<T; return 0; }