KMP
前缀函数
- 定义
对于一个长度为 \(n\) 的字符串 \(s\)，其前缀函数 \(\pi\) 定义为一个长为 \(n\) 的数组，其中 \(\pi[i]\) 定义为该字符串前缀子串 \(s[0\sim i]\) 的最长的相等的真前缀与真后缀的长度。
即：
特别的，定义 \(\pi[0]=0\)。
- 计算
性质1：对于 \(i\)，若 \(s[i+1]=s[\pi[i]]\)，则 \(\pi[i+1]=\pi[i]+1\)。
性质2：对于 \(i\)，若 \(s[i+1]\not =s[\pi[i]]\)，则 \(\pi[i+1]=j_{\min(k)},j_{n+1}=\pi[j_{n}-1],(j_{n}>0),\text{st}:s[i+1]=s[j_k]\)。
那么可以写出代码：
int pi[N];
char s[N];
int n=strlen(s);
for(int i=1;i<n;i++){
int j=pi[i-1];
while(j&&s[i]!=s[j]) j=pi[j-1];
if(s[i]==s[j]) j++;
pi[i]=j;
}
时间复杂度为 \(O(n)\)，这是因为 \(i,j\) 均移动 \(O(n)\) 次。
模式串匹配
- 计算模式串 \(s\) 在文本串 \(t\) 中的出现次数及出现下标
构造一个新字符串 \(e=s+\&+t\)，其中 \(\&\) 为一个在和 \(t\) 中均不出现的字符。
计算 \(e\) 的前缀函数。
若 \(\pi[i]=n,i>=n+1\)，则 \(s\) 出现了一次，其出现下标为 \(i-2n\)。
字符串周期
若 \(s\) 可以由长度为 \(p\) 的字符串 \(t\) 拼接而成（可以多余），那么 \(p\) 就是 \(s\) 的周期。
在 \(s\) 的所有周期中最小的一个叫做 \(s\) 的最小周期。
若 \(s\) 可以由长度为 \(p\) 的字符串 \(t\) 拼接而成（不可以多余），那么 \(p\) 就是 \(s\) 的真周期。
最小真周期的定义类似于最小周期。
- 计算 \(s\) 的最小周期及最小真周期
计算 \(s\) 的前缀函数。
则 \(n-\pi[n-1]\) 为 \(s\) 的最小周期。
若 \((n-\pi[n-1])|n\)，则 \(n-\pi[n-1]\) 为 \(s\) 的最小真周期，否则 \(s\) 不存在最小真周期。
前缀出现次数
- 给定一个长度为 \(n\) 的字符串 \(s\)，求出 \(s\) 的每个前缀在 \(s\) 中的出现次数。
for(int i=0;i<n;i++) ans[pi[i]]++;
for(int i=n-1;i>0;i--) ans[pi[i-1]]+=ans[i];
for(int i=0;i<n;i++) ans[i]++;
在上述代码中我们首先统计每个前缀函数值在数组 \(\pi\) 中出现了多少次，然后再计算最后答案：
如果我们知道长度为 \(i\) 的前缀出现了恰好 \(\text{ans}[i]\) 次，那么该值必须被叠加至其最长的既是后缀也是前缀的子串的出现次数中。在最后，为了统计原始的前缀，我们对每个结果加 \(1\)。
- 给定一个长度为 \(n\) 的字符串 \(s\)，求出 \(s\) 的每个前缀在另一个字符串 \(t\) 中的出现次数。
构造一个字符串 \(s+\text{&}+t\) 并计算其前缀函数。与第一个问题唯一的不同之处在于，我们只关心与字符串 \(t\) 相关的前缀函数值，即 \(i\ge n+1\) 的 \(\pi[i]\)。有了这些值之后，我们可以同样应用在第一个问题中的算法来解决该问题。