前缀函数与KMP算法

真前缀： S中不全等于S的前缀

前缀函数定义

\(s[0\dots i]\) 的真前缀与真后缀相等的最大长度为 \(\pi(i)\) 。

规定 \(\pi(0)=0\) 。

计算前缀函数

1.朴素算法

按照定义 , 按 \(i=1\dots n-1\) 计算 \(\pi(i)\) 。

令长度 \(j\) 从最大前缀长度 \(i\) 开始一直到 \(0\) 。

用 \(substr()\) 截取 \(s[0\dots j-1]\) 和 \(s[i-j+1,i]\)

若相等，则 \(\pi(i) =j\) ，否则 \(j--\) ,直到 \(j<0\) 时，\(\pi(i)=0\) 。

代码

vector<int> prefix_function(string s)
{
	int n = s.length();
	vector<int> pi(n);
	for(int i=1;i<n;++i) {
		for(int j=i;~j;--j)
		{
			if(s.substr(0,j) == s.substr(i-j+1,j))
			{
				pi[i] = j;
				break;
			}
		}
	}
	return pi;
}

2.优化一

\(\pi(i+1) <= \pi(i)+1\) ;

因为相当于在 \(s[0-i]\) 后加了一个 \(s[i+1]\) ,最大后缀最多增加 \(1\)

所以 相对于前一段代码 \(j = i\dots 0\) ，优化为 \(j=\pi(i-1)+1\dots 0\) 。

代码：

vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++)
    for (int j = pi[i - 1] + 1; j >= 0; j--)  // improved: j=i => j=pi[i-1]+1
      if (s.substr(0, j) == s.substr(i - j + 1, j)) {
        pi[i] = j;
        break;
      }
  return pi;
}

3.优化二

第一个优化中，我们考虑了 \(\pi(i+1)=\pi(i)+1\) 的最优情况，那么当最优情况不成立时，跳转到一个次优情况。

我们找到仅次于 \(\pi(i)\) 的第二长度 \(j\) ,使\(s[0\dots j-1]=s[i-j+1\dots i]\) 。

显然 \(j\) 是此时的最好选择。

这时若 \(s[j]=s[i+1]\) ，那么 \(\pi(i+1)=j+1\) 。

如下图：

可以看出，\(j\) 等价于 \(s[0\dots \pi(i)-1]\) 的前缀函数，即\(j=\pi(\pi(i-1))\) ；同理 ，次于 \(j\) 的第二长度 \(j^{(2)}=\pi(j-1)\) 。

得到关于 \(j\) 的状态转移方程：

\(j^{(n)} = \pi(j^{(n-1)}-1)\) , \(j^{(n-1)}>0\) 。

终极算法：

vector<int> prefix_function(string s)
{
    int n = s.length();
    vector<int> pi(n);
    for(int i = 1; i < n ; i++)
    {
        int j = pi[i-1];
        while(j>0 && s[i]!=s[j]) j = pi[j-1];
        if(s[i]==s[j]) ++j;//找到了满足条件的 j,j++后从i-1转移到 i
        pi[i] = j;
    }
    return pi;
}

前缀函数应用：KMP算法

对于一个文本 \(s_1\) 和一个匹配串 \(s_2\) ，求出 \(s_2\) 在 \(s_1\) 中所有出现的位置。

解法：

将 \(s_2\) 和 \(s_1\) 放在一个串 \(s\) 里， 用分隔符隔开。设 \(s_2\) 长度为 \(n\) 。

对 \(s\) 求前缀函数，由于分隔符(位置在 \(n\) )的存在， \(n\) 以后的所有\(\pi(i)\) 都不可能超过 \(n\) ,当 \(\pi(i)==n\) 时，意味着最长前缀等于最长后缀，且最长前缀长度为 \(n\) ,这个最长前缀就是 \(s_2\) 。

那么 \(s_2\) 在 \(s_1\) 中的位置就是 \(i-2\times \pi(i)\) ，下标 \(0\) 开始。

洛谷P3375 【模板】KMP字符串匹配

代码：

#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
using namespace std;
const int maxn = 1e6+7;
string s1,s2;
void prefix_function(string s,vector<int>& pi) // pi直接传进函数里
{
	int n = (int)s.length();
	for(int i = 1; i < n; ++i) 
    {
    	int j = pi[i-1];
		while(j>0 && s[i]!=s[j]) j = pi[j-1];
		if(s[i]==s[j]) ++j;
		pi[i] = j; // 若 j = 0 ,则说明 s[i] != s[j] 
    }
    return ;
} 
int main()
{
	freopen("data.in","r",stdin);
	string s;
	cin>>s1>>s2;
	s = s2 + '$' + s1; // 分隔符隔开
	//cout<<s<<endl; 
	int lens2 = (int)s2.length();
	int n = (int)s.length();
	//cout<<lens2<<" "<<n<<endl;
	vector<int> pi(n);
	prefix_function(s,pi);
	for(int i=lens2+1;i<=n;++i) // 下标0
	{
		if(pi[i] == lens2)
		{
			printf("%d\n",i-2*lens2+1);
		} 
	} 
	pi.clear();
	prefix_function(s2,pi);
	for(int i=0;i<lens2;++i) 
	{
		cout<<pi[i]<<" ";
	} 
	return 0;
} 

\(end\)

.......了吗？

被巨佬拜访后,我重审了KMP，发现 OI-Wiki 上的做法不是 KMP 的理解方式，只是对前缀函数的naive使用。

实际上 KMP 算法的流程：

• 对模式串求 pi，计入pi数组；
• 拿模式串和文本串匹配 长度 \(j\) ;

这两个过程本质都是求前缀函数，只是一个是自己匹配自己，另一个是自己匹配别人。

同时，在 KMP 算法里，\(\pi\) 数组被称为 失配数组，正如它的名字，当匹配不成立时，失配数组中的值就是当前次优状态，通过失配数组跳至这个次优状态。

代码：

#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
using namespace std;
const int maxn = 1e6+7;
int ls,lt;
void prefix_function(string s,vector<int>& pi) // pi直接传进函数里
{
	int n = (int)s.length();
	for(int i = 1; i < n; ++i) 
    {
    	int j = pi[i-1];
		while(j>0 && s[i]!=s[j]) j = pi[j-1];
		if(s[i]==s[j]) ++j;
		pi[i] = j; // 若 j = 0 ,则说明 s[i] != s[j] 
    }
    return ;
} 
string s,t;
void match(vector<int>& pi)//模式串匹配文本串
{
	int j=0;
	for(int i=0;i<ls;++i)
	{
		for(;j&&s[i]!=t[j];j=pi[j-1]);
		if(s[i]==t[j]) ++j;
		if(j==lt) printf("%d\n",i-lt+2); 
	}
}
int main()
{ios::sync_with_stdio(0);
	cin>>s>>t;
	ls = (int)s.length(); 
    lt = (int)t.length();
    vector<int> pi(lt);
    prefix_function(t,pi);
    match(pi);
    for(int i=0;i<lt;++i) printf("%d ",pi[i]);
	return 0;
} 

为了与国际接轨，我从 2022/07/13 开始做出以下规定：

• 字符串下标 0 开始；
• \(pi[i]\) 表示长度为 \(i\) 的前缀的失陪长度；

这样，KMP的模板就变成了：

void get_KMP(string s)
{
    int n = (int)s.length();
    int j  = 0; //请注意，j是当前匹配长度
    pi[0] = 0;
    for(int i=1;i<n;++i)
    {
        while(j&&s[i]!=s[j]) j = pi[j];//
        j+=(s[j]==s[i]);
        pi[i+1] = j; // i 是下标，i+1 是长度 
    }
}

神题：P2375 [NOI2014] 动物园

这题让求每个前缀的不重叠KMP个数。

即 \(最长前后缀 \le len/2\) ；

那么从 下标 \(0\dots n-1\) 重新依次匹配，原来求得的 \(pi\) 不能再用；

因为原先的 \(pi\) 可能包含重叠区域 ，而我们要的最长前后缀不能有重叠；

所以根据KMP的思想，用现在的合法最长前后缀推下一个；

题目要求每个前缀的所有不重叠匹配串，

假如 \(j\) 长度合法 , 那么下一个合法的就是 \(pi[j]\) , 下下个就是 \(pi[pi[j]]\) \(\dots\) 一直到 \(0\) (0不计数)

\(num\) 数组实际上是当前的 \(j\) 能跳失配指针几次到 0 ；

而板子中 \(pi[i+1]=j\) ,正是把 \(i+1\) 的失配指针作为 \(j\) 。

所以 \(num\) 的递推方式是: num[i+1]=num[j]+1;

此题就完结了；

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6+3;
const int mod = 1e9+7;
int pi[maxn],num[maxn],pre[maxn];
void get_KMP(string s)
{
	int j=0; pi[0]=0; pre[0] = 0, pre[1] = 1;
	int n = (int)s.length();
	for(int i=1;i<n;++i)
	{
		while(j && s[i]!=s[j]) j = pi[j];
		if(s[i]==s[j]) ++j;
		pi[i+1] = j;
		pre[i+1] = pre[j] + 1; //递推
    }
}
signed main()
{ios::sync_with_stdio(0);
	int T; cin>>T;
	for(;T--;)
	{
		string s;
		cin>>s;
		int n = s.length();
		memset(pi,0,sizeof(pi));
		memset(pre,0,sizeof(pre));
		memset(num,0,sizeof(num));
		get_KMP(s);
		int ans = 1;
		int j=0;
		for(int i=1;i<n;++i)
		{
			while(j && s[i]!=s[j]) j = pi[j];
		    if(s[i]==s[j]) ++j;
			while(j+j > (i+1)) j=pi[j];
			ans = (ans * (pre[j]+1) %mod);
		} 
		cout<<ans<<'\n';
	}
	return 0;
}