KMP

设文本串为长度为n的字符串T
模板串(匹配串)为长度为m的字符串P

复杂度$O(n+m)$

原理

将模式串表示为状态机,正向为匹配边,反向为失配边(对应结点为失配函数的值)。
如模式串 abcdabd
状态机

每次匹配失败就走失配边,然后重新从当前结点重新开始匹配。
重点在于失配函数的计算,可以理解为模式串自己与自己匹配。

  • 失配函数另一种理解方式: 匹配失败而终止时的字符串的后缀与前缀的最大重合部分

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int f[maxm];
char P[maxm],T[maxn];

void getFail(char *P,int f[])
{
int m = strlen(P);
f[0] = f[1] = 0;
for(int i=1;i<m;++i)
{
int j = f[i];
while(j && P[j]!=P[i]) j = f[j];
f[i+1] = P[j] == P[i] ? j+1 : 0;
}
}

int find(char *T,char *P,int f[])
{
int m = strlen(P);
int n = strlen(T);
int res = 0;
int j = 0;
for(int i=0;i<n;++i)
{
while(j && P[j]!=T[i]) j = f[j];
if(P[j]==T[i]) ++j;
if(j==m)
{
++res;
j = f[j];
}
}
return res;
}

扩展KMP

求模式串P与T的最长公共前缀。

AC自动机

当模式串有多个时我们在模式串的Tire上建立状态机,称为AC自动机。