KMP算法

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
void buildnext(string b,int next[])
{
	int m = b.size();
	int k= next[0] = -1;
	for (int j = 0; j + 1 < m; j++)//已知next[j],求next[j+1]
	{
		while (k != -1 && b[k] != b[j])
			k = next[k];
		next[j + 1] = ++k;
	}
}
int KMP(string a, string b)
{
	int n = a.size();
	int m = b.size();
	int next[N];
	buildnext(b, next);
	int i = 0, j = 0;
	while (i < n && j < m)
	{
		if (j == -1 || a[i] == b[j])//无相等前后缀或相等，i++,j++
			i++, j++;
		else j = next[j];//否则j回退到最长相等前后缀处
	}
	return j==m?i-m:-1;
}

拓展 所有匹配位置

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
void buildnext(string b,int next[])
{
	int k=next[0]=-1;
	for(int j=0;j+1<=m;j++)//要多算一位
	{
		while(k!=-1&&b[j]!=b[k])
			k=next[k];
		next[j+1]=++k;
	}
}
void KMP(string a,string b)
{
	int n=a.size();
	int m=b.size();
	int next[N];
	int i=0,j=0;
	int cnt=0;
	while(i < n && j < m)
	{
		if(j==-1 || a[i]==b[j] )
			i++,j++;
		else
			j=next[j];
		if(j==m)
		{
			cnt++;
			cout<<i-m<<endl;
			j=next[j];//”假装“此处失配,重新确定下次匹配位置
		}
	}
}

kMP隐藏应用

字符串长度为n

  • 最长相等前后缀长度：next[n]
  • 第二长相等前后缀长度：next[next[n]]
  • 最长重复前缀/后缀：next数组中的最大值max(next[i])

将next数组变为最小相等前后缀

1
2
3
4
5
6
7
8
9
10
11

void buildnext2(string a,int next[])
{
    int n=a.size();
    for(int j=1;j<=n;j++)
    {
        if(next[j]==0) continue;
        while(next[next[j]]!=0)
            next[j]=next[next[j]];
    }
}