原理有点太绕了,找时间补上,先贴代码
#include<iostream> #include<string> using namespace std; int* Next; int KMP(char* Str, char* SubStr); void NextTable(char* Str); int main(void) { string A, B; cin >> A; cin >> B; char* Str=const_cast<char*>(A.c_str()); char* SubStr=const_cast<char*>(B.c_str()); //cout << Str << endl << SubStr << endl; Next = new int[strlen(Str)]; NextTable(Str); cout << KMP(Str, SubStr) << endl; system("pause"); return 0; } int KMP(char* Str, char* SubStr) { int i = 0; int j = 0; while (i < strlen(Str) && j < strlen(SubStr)) { if (j == -1 || Str[i] == SubStr[j]) { i++; j++; } else j = Next[j]; } if (j == strlen(SubStr)) return i - j; else return -1; } void NextTable(char* Str) { int i = 0, j = -1; Next[0] = -1; while (i < strlen(Str)) { if (j == -1 || Str[i] == Str[j]) { ++i; ++j; Next[i] = j; } else j = Next[j]; } }