算法思想代码实现int* getnext() { int* next new int[s2.size()]; int j 0;//用来遍历子串 int k -1;//子串中公共子串的长度 next[0] -1; while (j s2.size() - 1) { if (k-1||s2[k] s2[j]) { k; j; if (s2[k] s2[j]) { next[j] next[k]; } else { next[j] k; } } else { k next[k];//做k值得回溯继续找最长公共前后缀 } } return next; } int KMP() { { int i 0; int j 0; //是为了处理当j-1时的情况 int len1 s1.size(); int len2 s2.size(); int* next getnext(); while (i len1 j len2) { if (j-1||s1[i] s2[j]) { i; j; } else { j next[j]; } } if (j s2.size()) { return i - j; } else { return -1; } } } int main() { int pos KMP(); cout pos endl; return 0; }