KMP 练习题
在竞赛中 KMP 已经考的比较少了，然而习题还是要做的。
KMP 的练习题目一般是围绕着 (next) 数组和 (f) 数组的不同理解出发的，具体请看例题。
T1 [BOI2009]Radio Transmission 无线传输
题目链接：Link
题目描述：
给定一个字符串 (A) ，(A) 是由另一个字符串 (B) 不断循环拼接而成的（可能不是整数个 (B)），求 (B) 可能长度的最小值。
Solution：
这道题目不难，但是如果自己独立思考想出解法，可以极大提升对 KMP 算法 (next) 数组的理解。
首先，假设这个字符串最短的长度为 (k) ，那么 (A_{k+1} ightarrow A_{k+k}) （假设 (A) 长度 (N) ，(N>2k)）一定等于 (A_1 ightarrow A_k) 。如果对 (A) 进行自我匹配，求出 (next) 数组，则 (next_{k+1} ightarrow next_{N}) 应该成首项为 1 ，公差为 1 的等差数列，因为第一个 (B) 串一定可以和第二个、第三个、第 (n) 个 (B) 串完全匹配，如下表：
1 2 3 4 5 6 7 8 9...
a a b a a a b a a...
next 0 1 0 1 1 2 3 4 5...
(next_5) 是这个等差数列的第一项，那么这个等差数列的最后一项为 (next_8=5) ，根据等差数列的公式得知项数 (n) 等于 最后一项 (next_8) 的值。又因为答案为这个等差数列第一项的前一项，所以最后答案就是 (n-next_n) 。
Code：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
//using namespace std;
const int maxn=1000005;
int n;
char str[maxn];
int next[maxn];
void kmp(){
next[1]=0;
for(int i=2,j=0;i<=n;++i){
while(j>0 && str[i]!=str[j+1]) j=next[j];
if(str[i]==str[j+1]) j++;
next[i]=j;
}
printf("%d
",n-next[n]);
}
signed main(){
scanf("%d",&n);
scanf("%s",str+1);
kmp();
return 0;
}
T2 UVA1328 Period
题目链接：Link
题目描述：
洛谷上给出的翻译比较简略，这里重新翻译一下题面。（原版英文题面）
给定字符串长度 (N(Nleq 1e6)) ，然后给出一个长度为 (N) 的字符串 (A) 。
如果对于 (A) 的前 (i) 个字符是严格循环同构的（由一个字符串 (B) 首尾相连 (n(ngeq 2)) 次构成），输出 (i,n) 。
有多组数据，如果 (N=0) 表示输入结束。
Solution：
本题和 T1 有异曲同工之处，类似 T1 的思路，先对字符串跑 KMP 求出 (next) 数组。
利用上面的结论，如果一个字符串从第一项开始循环同构，那么它的最小循环节为 (i-next_i) 。
假设字符串 (A) 的某个前缀长度为 (i) ，已经求出它的最小循环节，则这个循环节出现的次数应该是 (frac{i}{i-next_i}) 。
根据题目要求，答案应该满足 (frac{i}{i-next_i}geq 2，i\%frac{i}{i-next_i}=0) ，于是扫描 (next) 数组，输出答案即可。
Code：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
//using namespace std;
const int maxn=1000005;
char str[maxn];
int next[maxn];
int n=1,cas;
void kmp(){
next[1]=0;
for(int i=2,j=0;i<=n;++i){
while(j>0 && str[i]!=str[j+1]) j=next[j];
if(str[i]==str[j+1]) j++;
next[i]=j;
}
printf("Test case #%d
",cas);
for(int i=2;i<=n;++i){//扫描、判断答案是否合法
if(next[i]*2>=i && i%(i-next[i])==0)
printf("%d %d
",i,i/(i-next[i]));
}
puts("");
}
signed main(){
while(n){
scanf("%d",&n);
if(n){
cas++;
scanf("%s",str+1);
kmp();
}
}
return 0;
}
T3 [USACO15FEB]Censoring S
题目链接：Link
题目描述：
给定两个字符串 (A) ，(B) 要求从 (A) 中不断删除找到的第一个 (B) ，然后拼接剩下的串，输出删除后的串。
注意：删除之后，两端的 (A) 串剩余部分可能会再拼成一个 (B) 串
Solution：
设 (A) 长度为 (n) ，(B) 的长度为 (m) 。
显然这题是字符串匹配题，要从 (A) 中匹配 (B) ，可以使用 KMP 查找 (B) 的位置。
这里删除操作不影响 (B)，所以先跑 KMP 的第一阶段，求出 (B) 的 (next) 数组。
然后，还是一位一位地求解 (f) 数组，如果还没和 (B) 串匹配上，就把这一位的 (A) 加入答案串，答案串长度++。
如果匹配上了，把答案串删掉 (m) 位，然后从 (m) 位之前重新开始匹配。
注意这个操作需要更新 (j) 的值为上一个答案的 (f) 值，这样相当于忽略了中间的 (m) 个字符继续进行匹配操作。
由于数组不太好操作，这里我使用了 STL stack 来实现记录答案和更新 (j) 的操作。
Code：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stack>
//using namespace std;
const int maxn=1000005;
char A[maxn],B[maxn];//A原串,B模式串
int lena,lenb;
int next[maxn],f[maxn];
std::stack<char>stk;
std::stack<int>s;
char ans[maxn];
void kmp(){
next[1]=0;
for(int i=2,j=0;i<=lenb;++i){
while(j>0 && B[i]!=B[j+1]) j=next[j];
if(B[i]==B[j+1]) j++;
next[i]=j;
}
s.push(0);//这是为了防止把元素全弹出去后 j=s.top() 操作导致 RE
for(int i=1,j=0;i<=lena;++i){
while(j>0 && A[i]!=B[j+1]) j=next[j];
if(A[i]==B[j+1]) j++;
f[i]=j;
stk.push(A[i]);
s.push(f[i]);//表示这一位答案的 f 值
//其实为了减小常数应该开结构体存，但是因为懒就用两个同步栈代替了
if(f[i]==lenb){
for(int k=1;k<=lenb;++k)
stk.pop(),s.pop();
j=s.top();//弹完后 j 更新为栈顶元素的 f ，也就是 m 个元素之前的那个 f 值
}
}
int num=stk.size();
for(int i=1;i<=num;i++){
ans[i]=stk.top();
stk.pop();
}
for(int i=num;i>=1;--i)
putchar(ans[i]);
}
signed main(){
scanf("%s%s",A+1,B+1);
lena=std::strlen(A+1);
lenb=std::strlen(B+1);
kmp();
return 0;
}
T4 [POI2006]OKR-Periods of Words
题目链接：Link
题目描述：
给定一个长度为 (N) 的字符串 (A) ，若一个非 (A) 本身的串 (Q) 是 (A) 的前缀，且 (A) 是 (Q+Q) 的前缀，则称 (Q) 是 (A) 的周期（ (Q) 可以为空），求 (A) 的所有前缀的最大周期串长度之和。
Solution：
对于长度为 (i) 的串，要满足的条件 (A_1 ightarrow A_i) 是 (Q+Q) 的前缀。想要满足这个条件，(next_i) 必须大于 0 。（ (next_i) 的另一个定义是：模式串长度为 (i) 的前缀，其前缀和后缀相等的最长长度。这个性质可以简单地根据 KMP 的原理得出，这里不再赘述。）
假设蓝色为模式串长度为 (i) 的前缀，红色为 (next_i) ，如果从前后缀第一个不相等的位置截为 (Q) （绿色），那么把 (Q') 拼在后面正好可以让红色的部分重合，而且使得 (Q) 的长度最长。
另外还有一个条件，显然 (Q) 的长度至少为 (frac i 2) 。
既然要使得 (Q) 的长度最长，那么势必要让 (next_i) （红色）部分最短。不巧的是，KMP 算法求出的是最大可能的 (next_i) 。记得求 (next) 数组时的证明吗？(next_i) 所有的可能值是 next[i],next[next[i]],next[nxet[next[i]]]... 我们可以递归访问 (next) 数组来得到它的最小值 (p)，此时 (Q) 长度最长，为 (i-p) 。
但是有这样一个问题，如果这个字符串全都是同一个字符（比如 'a' ），那么我们每次递归只能向前跳一个字符，这样导致每找一次长度为 (i) 的前缀的“周期”就要递归 (i-1) 次，这样总复杂度退化到 (O(n^2)) 。
要解决这个问题，就得防止递归次数退化。我联想到了并查集的路径压缩方法，并查集的做法是：在查询到 (x) 的父亲时顺便把 (x) 及其子树直接挂到它父亲的下面。那么我们为什么不在查询到 (next_i) 时直接把它修改为最小值呢？
优化以后，时间复杂度 (O(n)) 。
Code：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
//using namespace std;
const int maxn=1000005;
char str[maxn];
int n;
long long ans;//第一次交不开long long见了祖宗
int next[maxn];
void kmp(){
next[1]=0;
for(int i=2,j=0;i<=n;++i){
while(j>0 && str[i]!=str[j+1]) j=next[j];
if(str[i]==str[j+1]) j++;
next[i]=j;
}
for(int i=2,j=2;i<=n;++i,j=i){
while(next[j]) j=next[j];//找最小的next[i]的可能值
if(next[i]) next[i]=j;//类似路径压缩
ans+=i-j;//更新答案
}
printf("%lld
",ans);
}
signed main(){
//freopen("P3435_13.in","r",stdin);
scanf("%d",&n);
scanf("%s",str+1);
kmp();
return 0;
}
T5 [NOI2014] 动物园
这个题我想了一下午，然而并没有想出怎么优化 (O(Tn^2)) 的复杂度到 (O(Tn)) ，于是口胡了一个 (O(Tnlogn)) 的做法。
吸氧 之后以最慢点 537ms 草过去了（(nlogn) 还是快啊）。
题目链接：Link
题目描述：
给定一个长度为 (N) 的字符串 (A) ，求出 (num) 数组。其中 (num_i) 表示 (A) 的长度为 (i) 的前缀 (P)，满足既是 (P) 的前缀又是 (P) 的后缀，且长度 (kleq frac i 2) 的子串 (Q) 的个数。
为了避免大量输出，只要求输出：(prodlimits_{i=1}^Nnum_i+1 mod 1e9+7) 的值。
Solution：
在叙述解法之前，想问读者一个问题：
- 关于 (next) 数组的递归访问，以及前面 T4 中提到的类似并查集路径压缩优化，你有没有想到什么？
显然，(next) 数组是一棵以 0 为根的带权树。想想吧，不管我们从哪里开始递归访问，总能访问到 (next_i=0) 。
除此之外，(next) 树还有一个十分重要的性质：对于每棵非空子树，根节点权值一定小于子节点权值——这是 (next) 数组的定义导致的。根据 (next) 的定义，不难发现：(next_i<i) ，故每个节点的父节点权值一定小于子节点权值。
回到本题，先 KMP 预处理出 (next) 数组。很显然，对于每一个 (i) ，它的 (next_i) 就表示可能的 (Q) 的长度（参考 T4 中给出的 (next) 数组的另一个定义）。我们不断的递归访问其 (next) ，如果这个 (next) 值小于 (frac i 2) ，那么说明这个 (next) 代表一个合法的 (Q) 串，不断递归操作，直到访问到 0 为止，就找出了对于 (i) 的所有的合法的 (Q) 串。
但是，还是 T4 中的问题，这样做会被全是相同字符的数据把复杂度卡到 (O(n^2)) 。
考虑优化：对于每个 (i) ，其 (next) 的访问顺序都是一条权值单调递增的带权链（第 (i) 个节点的权值是 (next_i)）。这样可以使用 ST 算法在 (logn) 的时间内查询权值小于 (k) 的第一个节点位置。利用这个性质可以查询权值小于 (frac i 2) 的第一个节点 (v)，那么 (v) 前面的节点权值必然小于 (frac i 2) ，也就是说，(forall iin[1,v],next_i=Q) ，且这些 (Q) 都合法。要统计答案的话，再从 (v) 出发，倍增找出它前面有多少个节点，计入答案就行了。
另外，实际操作的时候要把这 (n) 条链建成一棵树，不然开不下那么大的空间，预处理也会超时的。
Code：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
//using namespace std;
#define ll long long
#define mod 1000000007
const int maxn=1000005;
int N,n;
char str[maxn];
int next[maxn];
int f[20][maxn];
//f[i][j] 表示 j的2^i 祖先，量小的做第一维，空间连续性更强，会更快！
//2^20=1.4e6 卡满常数，否则可能TLE
ll sum=1;
void kmp(){
next[1]=0;
for(int i=2,j=0;i<=n;++i){
while(j && str[i]!=str[j+1]) j=next[j];
if(str[i]==str[j+1]) j++;
next[i]=j;
f[0][i]=j;
}
for(int i=1;i<20;++i)
for(int j=1;j<=n;++j)
f[i][j]=f[i-1][f[i-1][j]];
sum=1;
for(int i=2;i<=n;++i){
int p=i;
for(int j=19;j>=0;--j)
if(f[j][p]*2>i) //现在的 p 不合法
p=f[j][p];//跳到 p 的 2^j 祖先
ll tot=0;
for(int j=19;j>=0;--j)
if(f[j][p])
tot+=1<<j,p=f[j][p];//这一蹦，蹦过了 2^j 个节点，也就是有 2^j 个合法方案
sum=sum*(tot+1)%mod;//统计答案
}
printf("%lld
",sum);
}
signed main(){
scanf("%d",&N);
while(N--){
scanf("%s",str+1);
n=std::strlen(str+1);
kmp();
}
return 0;
}
写在最后
特别鸣谢：
李煜东在《算法竞赛进阶指南》中和 二gou子(徐队) 提供的 KMP 好题。