设n为待匹配字符串的字符个数 m为目标字符串的字符个数 使用kmp查找字符串位置，时间复杂度为O(n+m) 根本原理是利用目标字符串提供的前缀后缀信息进行快速匹配， 下例中设m=5
待匹配字符串 “aaaacaaaacaaaaa” 下标j0 1 2 3 4目标字符串a a a a anext-1 0 1 2 3发挥最差性能，当下标4不匹配时，目标字符串后移1位与待匹配字符串比较。目标字符串的前3个字符均已配对。直接将第4个字符与待匹配的字符串之前未匹配的字符进行比较。 2. 待匹配字符串"abcdabcdabcde"
下标0 1 2 3 4目标字符串a b c d enext-1 0 0 0 0发挥最佳性能，当下标4不匹配时，目标字符串后移4位与待匹配字符串比较。目标字符串的所有字符均还未配对。从第1个字符与待匹配字符串之前未匹配的字符进行比较。
#include <iostream> #include <vector> #include <string> using namespace std; vector<int> getNext(string T) { vector<int> next(T.size(), 0); next[0] = -1; // next矩阵的第0位为-1 int k = 0; // k值 for (size_t j = 2; j < T.size(); ++j) // 从字符串T的第2个字符开始，计算每个字符的next值 { while (k > 0 && T[j - 1] != T[k]) k = next[k]; if (T[j - 1] == T[k]) k++; next[j] = k; } return next; int KMP(string S, string T) { vector<int> next = getNext(T); int i = 0, j = 0; while (S[i] != '\0' && T[j] != '\0') { if (S[i] == T[j]) { ++i; ++j; } else { j = next[j]; } if (j == -1) { ++i; ++j; } } if (T[j] == '\0') return i - j; else return -1; } int main() { string S; string T; cout << "输入代查找字符串：" << endl; cin >> S; cout << "输入目标字符串：" << endl; cin >> T; int num = KMP(S, T); vector<int> a = getNext(T); for (unsigned int i = 0; i < a.size();i++) { cout << a[i] << " "; } cout << endl; cout << "位置" << num<<endl; system("pause"); return 0; }