KMP算法瞎扯

发表于 | 阅读次数：

KMP算法用来解决字符串匹配问题，能在$O(n)$的复杂度的内求出字符串匹配问题。

前置

我们首先要求出：对于模式串，$p[i]$ 表示模式串$1-i$ 的这个串中首尾相同的最大长度是多少。

那么对于$p[i]$ 假如我们已经求出前$i-1$ 的p值，那么我们就得重新回到已经匹配过的最大相同部分，给出一个例子

$ababaabb$

00123120

下面这行就是求得的p值

也就是说，当i向后移一位时，j的后一位就要看匹不匹配，否则，我们就一直跳，j跳到p[j],就是找到另一个与现p[j]相同的前后缀，继续看是否匹配。

如果相同，那么p[i]就是当前的p[j]+1。

其实，

算法流程

KMP在匹配过程中先同暴力一样，匹配到一位就继续向后匹配，但是遇到了不一样的字符时，那么刚才预处理的p数组就派上用场了。我们只需要将模式串的指针$j $跳到$p[j]$ 即可。

匹配完成的条件就是$j==模式串长度$ ,匹配完成后j不能为0，而是再跳一次

代码

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
34

scanf("%s",s+1);
int st=strlen(s+1);
int j=0;
for(register int i=2;i<=st;++i)
{
	while(j&&s[j+1]!=s[i])
	{
		j=p[j];
	}
	if(s[j+1]==s[i])
	{
		j++;
	}
	p[i]=j;
}

j=0;
for(register int i=1;i<=la;++i)
{
	while(j&&s[j+1]!=aa[i])
	{
		j=p[j];
	}
	if(s[j+1]==aa[i])
	{
		j++;
	}
	if(j==st)
	{
		ans++;
		j=0;
	}
}