前缀函数与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\) 开始。
代码：
#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 是长度
}
}
这题让求每个前缀的不重叠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;
}