久仰字符串系列理论
KMP
讲解（引用自bzoj3670动物园）
某天，园长给动物们讲解KMP算法。
园长：“对于一个字符串S，它的长度为L。我们可以在O(L)的时间内，求出一个名为next的数组。有谁预习了next数组的含义吗？”
熊猫：“对于字符串S的前i个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作next[i]。”
园长：“非常好！那你能举个例子吗？”
熊猫：“例S为abcababc，则next[5]=2。因为S的前5个字符为abcab，ab既是它的后缀又是它的前缀，并且找不到一个更长的字符串满足这个性质。同理，还可得出next[1] = next[2] = next[3] = 0，next[4] = next[6] = 1，next[7] = 2，next[8] = 3。”
作用
基础KMP算法是用来处理字符串匹配的问题的。最简单的应用便是纯粹的询问：A是否在B中出现过。
KMP最核心的内容莫过于fail[]（也叫做next[]）。对于这部分内容的理解可以考出比较多的花样（但似乎kmp的模型无非比较经典的那几个，我到现在为止见过最灵活的还是非主席树莫属）
KMP的例题
【kmp模板】P3375 【模板】KMP字符串匹配
题目描述
如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。
为了减少骗分的情况，接下来还要输出子串的前缀数组next。
（如果你不知道这是什么意思也不要问，去百度搜[kmp算法]学习一下就知道了。）
输入输出格式
输入格式：
第一行为一个字符串，即为s1
第二行为一个字符串，即为s2
输出格式：
若干行，每行包含一个整数，表示s2在s1中出现的位置
接下来1行，包括length(s2)个整数，表示前缀数组next[i]的值。
说明
时空限制：1000ms,128M
数据规模：
设s1长度为N，s2长度为M
对于30%的数据：N<=15，M<=5
对于70%的数据：N<=10000，M<=100
对于100%的数据：N<=1000000，M<=1000000
样例说明：
所以两个匹配位置为1和3，输出1、3
题目分析
基础KMP板子，先存着。
#include<bits/stdc++.h>
const int maxn = ; char A[maxn],B[maxn];
int fail[maxn],n,m; int main()
{
scanf("%s%s",A+,B+);
n = strlen(A+), m = strlen(B+);
fail[] = ;
for (int i=, j=; i<m; i++)
{
while (j&&B[j+]!=B[i+]) j = fail[j]; //不能继续匹配并且j没减到0，j回退
if (B[j+]==B[i+]) j++; //能继续匹配
fail[i+] = j;
}
for (int i=, j=; i<n; i++)
{
while (j&&B[j+]!=A[i+]) j = fail[j]; //不能继续匹配并且j没减到0，j回退
if (B[j+]==A[i+]) j++; //能匹配
if (j==m){ //匹配到了B串
printf("%d\n",i-m+);
j = fail[j]; //继续找匹配（因为有可能两处匹配重叠）
}
}
for (int i=; i<=m; i++) printf("%d ",fail[i]);
puts("");
return ;
}
【kmp略带理解】hdu2087剪花布条
Problem Description
Input
Output
题目分析
大意就是要在A中找出最多数量互不重叠的B串。于是每一次匹配完是将j清零就好了。
#include<bits/stdc++.h>
const int maxn = ; char A[maxn],B[maxn];
int fail[maxn],n,m,ans; int main()
{
while (scanf("%s",A+)!=EOF)
{
if (A[]=='#') break;
scanf("%s",B+);
n = strlen(A+), m = strlen(B+);
ans = fail[] = ;
for (int i=, j=; i<m; i++)
{
while (j&&B[i+]!=B[j+]) j = fail[j];
if (B[i+]==B[j+]) j++;
fail[i+] = j;
}
for (int i=, j=; i<n; i++)
{
while (j&&A[i+]!=B[j+]) j = fail[j];
if (A[i+]==B[j+]) j++;
if (j==m)
ans++, j = ;
}
printf("%d\n",ans);
}
return ;
}
【kmp理解】bzoj3670: [Noi2014]动物园
Description
近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。
某天，园长给动物们讲解KMP算法。
园长：“对于一个字符串S，它的长度为L。我们可以在O(L)的时间内，求出一个名为next的数组。有谁预习了next数组的含义吗？”
熊猫：“对于字符串S的前i个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作next[i]。”
园长：“非常好！那你能举个例子吗？”
熊猫：“例S为abcababc，则next[5]=2。因为S的前5个字符为abcab，ab既是它的后缀又是它的前缀，并且找不到一个更长的字符串满足这个性质。同理，还可得出next[1] = next[2] = next[3] = 0，next[4] = next[6] = 1，next[7] = 2，next[8] = 3。”
园长表扬了认真预习的熊猫同学。随后，他详细讲解了如何在O(L)的时间内求出next数组。
下课前，园长提出了一个问题：“KMP算法只能求出next数组。我现在希望求出一个更强大num数组一一对于字符串S的前i个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]。例如S为aaaaa，则num[4] = 2。这是因为S的前4个字符为aaaa，其中a和aa都满足性质‘既是后缀又是前缀’，同时保证这个后缀与这个前缀不重叠。而aaa虽然满足性质‘既是后缀又是前缀’，但遗憾的是这个后缀与这个前缀重叠了，所以不能计算在内。同理，num[1] = 0,num[2] = num[3] = 1,num[5] = 2。”
最后，园长给出了奖励条件，第一个做对的同学奖励巧克力一盒。听了这句话，睡了一节课的企鹅立刻就醒过来了！但企鹅并不会做这道题，于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出num数组呢？
特别地，为了避免大量的输出，你不需要输出num[i]分别是多少，你只需要输出
对1,000,000,007取模的结果即可。
Input
第1行仅包含一个正整数n ，表示测试数据的组数。随后n行，每行描述一组测试数据。每组测试数据仅含有一个字符串S，S的定义详见题目描述。数据保证S 中仅含小写字母。输入文件中不会包含多余的空行，行末不会存在多余的空格。
Output
包含 n 行，每行描述一组测试数据的答案，答案的顺序应与输入数据的顺序保持一致。对于每组测试数据，仅需要输出一个整数，表示这组测试数据的答案对 1,000,000,007 取模的结果。输出文件中不应包含多余的空行。
Sample Input
aaaaa
ab
abcababc
Sample Output
1
32
HINT
n≤5,L≤1,000,000
题目大意
kmp算法中所求的$fail[i]$代表$i$位置最长「相同的前缀后缀」；相似地，这里的$num[i]$代表$i$位置所有不重叠「相同的前缀后缀」的数量和。
题目分析
嘛……算是一道考察对于kmp算法理解的思维题。
每一次求next[]时舍去有重叠的最长前后缀是不行的，因为会对后面的转移造成影响。
那么考虑最基础的暴力，就是枚举每一个i再做kmp（感觉这个暴力可以用exKMP优化的样子，不过我不会）。显然复杂度是爆炸的。
继而考虑优化，先求出允许重叠的「相同的前缀后缀」的答案$prenum[]$，再考虑与当前情况不矛盾的$prenum[]$之和。这句话或许有点奇怪，换而言之就是：在之前允许重叠的答案里，找出一些对于当前情况来说，不重叠的答案之和。
好吧之后的过程我讲得就不甚清楚了，挂一篇博客吧[NOI2014][bzoj3670] 动物园 [kmp+next数组应用]
#include<bits/stdc++.h>
const int maxn = ;
const int MO = 1e9+; int prenum[maxn],fail[maxn];
int tt,n,ans;
char str[maxn]; int main()
{
scanf("%d",&tt);
while (tt--)
{
memset(fail, , sizeof fail);
scanf("%s",str);
n = strlen(str);
prenum[] = , prenum[] = , ans = ;
for (int i=, j=; i<n; i++)
{
while (j&&str[i]!=str[j]) j = fail[j];
if (str[i]==str[j]) j++;
fail[i+] = j, prenum[i+] = prenum[j]+;
}
for (int i=, j=; i<n; i++)
{
while (j&&str[i]!=str[j]) j = fail[j];
if (str[i]==str[j]) j++;
while ((j<<)>i+) j = fail[j];
ans = 1ll*ans*(prenum[j]+)%MO;
}
printf("%d\n",ans);
}
return ;
}
【完全最短循环子串】poj2406Power Strings
Description
Input
Output
Sample Input
abcd
aaaa
ababab
.
Sample Output
1
4
3
Hint
题目大意
多组数据，求一个字符串的最短循环子串
题目分析
注意到kmp中的$fail[i]$表示的是最大的前缀的后缀的长度，即$1...fail[n]$等同$n-fail[n]+1...n$。也就是说若原串是一个循环次数大于1的循环子串，那么$n-fail[n]$一段刚好是最短的循环子串。
当时我也想了一会儿才想清楚，这里放一张图。
#include<cstring>
#include<cstdio>
const int maxn = ; char ch[maxn];
int fail[maxn],n; int main()
{
while (scanf("%s",ch+))
{
if (ch[]=='.') break;
memset(fail, , sizeof fail);
n = strlen(ch+);
for (int i=, j=; i<n; i++)
{
while (j&&ch[i+]!=ch[j+]) j = fail[j];
if (ch[i+]==ch[j+]) j++;
fail[i+] = j;
}
if (n%(n-fail[n])==) printf("%d\n",n/(n-fail[n]));
else puts("");
}
return ;
}
【不完全最短循环子串】bzoj1355: [Baltic2009]Radio Transmission
Description
Input
Output
Sample Input
cabcabca
Sample Output
HINT
对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串
题目分析
数据保证了给定串为不完整的循环子串，那么算几组手造数据的$fail[]$会发现：
第二次循环节开始时，fail[]变为从一开始的递增序列。
要注意的是这并不意味着答案就是从首开始的零个数。
这是一个小细节。
#include<bits/stdc++.h>
const int maxn = ; char ch[maxn];
int n,fail[maxn]; int main()
{
scanf("%d%s",&n,ch+);
for (int i=, j=; i<n; i++)
{
while (j&&ch[i+]!=ch[j+]) j = fail[j];
if (ch[i+]==ch[j+]) j++;
fail[i+] = j;
}
printf("%d\n",n-fail[n]);
return ;
}
【fail[]巧妙运用】bzoj1511: [POI2006]OKR-Periods of Words
Description
Input
Output
Sample Input
babababa
Sample Output
题目分析
好困，大脑宕机。
先挂题解和代码：luoguP3435 [POI2006]OKR-Periods of Words
#include<bits/stdc++.h>
const int maxn = ; int n,fail[maxn];
char str[maxn];
long long ans; int main()
{
scanf("%d%s",&n,str+);
for (int i=, j=; i<n; i++)
{
while (j&&str[i+]!=str[j+]) j = fail[j];
if (str[i+]==str[j+]) j++;
fail[i+] = j;
}
for (int i=; i<=n; i++)
if (fail[fail[i]]) fail[i] = fail[fail[i]];
for (int i=; i<=n; i++)
if (fail[i]) ans += 1ll*i-fail[i];
printf("%lld\n",ans);
return ;
}
END