前缀函数与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;
}