KMP算法详解

KMP算法详解

本文数组使用1作为开始的下标,与0开头的版本有所不同。

$kmp$算法是一种高效的字符串匹配算法,通常来说,足以应付考试中的扯淡要求。

核心思想

在暴力算法中,若当前位两个字符串失配($a[i]!=b[j]$),我们将模式串向前挪动一位。

暴力算法

1
2
3
4
5
6
7
8
9
for(int i=1;i+m-1<=n;++i)
{
int j;
for(j=1;j<=m;++j)
if(a[i+j-1]!=b[j])
break;
if(j==m+1)
printf("Found at %d\n",i);
}

时间复杂度为$O(nm)$,显然,要想优化这个算法,必须要找到更优的在失配后的解决方案。

这就是维护一个$next$数组,使得当每次失配后,不需要从头开始继续匹配。

kmp

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1,j=0;i<=n;++i)//j的含义为“已经匹配的位数”
{
while(j&a[i]!=b[j+1])
j=nxt[j];
if(a[i]==b[j+1])
++j;
if(j==m)
{
printf("Found at %d\n",i-m+1);
j=nxt[j];
}
}

如果当前位失配,将j设为上一位的$next$值$+1$,继续进行匹配。

计算next数组

1
2
3
4
5
6
7
8
9
10
11
12
void getnext()//注意next是linux下的关键字哦~
{
nxt[1]=0;
for(int i=2,j=0;i<=len;++i)
{
while(j&&b[i]!=b[j+1])
j=nxt[j];
if(b[i]==b[j+1])
++j;
nxt[i]=j;
}
}

强烈建议自己动手推一遍,通过建立对算法的理解来记忆。

next的原理

那么,神奇的$next$是什么原理呢?

$next$数组存放的值,其实是模式串前i位的最长公共前后缀。

例如,ababcaba的$next$值为3,其最长公共前后缀为aba

所以,每当后一位失配时,我们将模式串向前移当前串的长度-最长后缀的长度,保证最长的前缀是匹配上的。

因此,$kmp$算法保证了在失配后将模式串向前移动的距离是最大的。