kmp模式匹配模板
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("匹配成功");
}
}
}