kmp算法的关键就是前缀和后缀
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std; const int MAX_LEN = 1e5 + 10; int n, len1, len2; char t[MAX_LEN], p[MAX_LEN]; int _next[MAX_LEN]; inline void get_next() { int i = 0, j; _next[0] = j = -1; while (i < len2) { if (j < 0 || p[i] == p[j]) { ++i; ++j; _next[i] = j; } else { j = _next[j]; } } } void kmp() { int i = 0, j = 0; while (i < len1) { if (j < 0 || t[i] == p[j]) { i++; j++; } else { j = _next[j]; } if (j == len2) { printf("匹配成功"); } } }