Part 5.2 KMP

>关于字符串的基础知识<

【模板】KMP

题目描述

给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l,r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。
现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。

定义一个字符串 $s$ 的 border 为 $s$ 的一个非 $s$ 本身的子串 $t$，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。
对于 $s_2$，你还需要求出对于其每个前缀 $s^{\prime }$ 的最长 border $t^{\prime }$ 的长度。

输入格式

第一行为一个字符串，即为 $s_1$。
第二行为一个字符串，即为 $s_2$。

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 $s_2$ 在 $s_1$ 中出现的位置。
最后一行输出 $|s_2|$ 个整数，第 $i$ 个整数表示 $s_2$ 的长度为 $i$ 的前缀的最长 border 长度。

样例 #1

样例输入 #1

ABABABC
ABA

样例输出 #1

1
3
0 0 1

提示

样例 1 解释

。

对于 $s_2$ 长度为 $3$ 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 $1$。

数据规模与约定

本题采用多测试点捆绑测试，共有 3 个子任务。

• Subtask 1（30 points）：$|s_1|\le 15$，$|s_2|\le 5$。
• Subtask 2（40 points）：$|s_1|\le 10^4$，$|s_2|\le 10^2$。
• Subtask 3（30 points）：无特殊约定。

对于全部的测试点，保证 $1\le |s_1|,|s_2|\le 10^6$，$s_1,s_2$ 中均只含大写英文字母。

code

对于第一问，当找到一处完全匹配的位置之后，令j=nxt[j]后继续匹配。
对于第二问，直接输出nxt数组的值即可，因为nxt数组的定义就是第i个位置相同前后缀的最大长度。

#include<iostream>
using namespace std;
#define MAX_N 1000000
string s1,s2;
int _next[MAX_N+5];
void get__next(string t)
{int tlen=t.size();_next[0]=-1;int j=-1;for(int i=1;t[i];i++){while(j!=-1&&t[i]!=t[j+1])j=_next[j];if(t[i]==t[j+1])j+=1;_next[i]=j;}return ;
}
void KMP(string s,string t)
{int tlen=t.size();int j=-1;for(int i=0;s[i];i++){while(j!=-1&&t[j+1]!=s[i])j=_next[j];if(t[j+1]==s[i])j+=1;if(t[j+1]==0){printf("%d\n",i-tlen+2);j=_next[j];} }return ;
}
int main()
{cin>>s1>>s2;get__next(s2);KMP(s1,s2);for(int i=0;i<s2.size();i++)printf("%d ",_next[i]+1);return 0;
}

[BOI2009] Radio Transmission 无线传输

题目描述

给你一个字符串 $s_1$，它是由某个字符串 $s_2$ 不断自我连接形成的（保证至少重复 $2$ 次）。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行一个整数 $L$，表示给出字符串的长度。

第二行给出字符串 $s_1$ 的一个子串，全由小写字母组成。

输出格式

仅一行，表示 $s_2$ 的最短长度。

样例 #1

样例输入 #1

8
cabcabca

样例输出 #1

3

提示

样例输入输出 1 解释

对于样例，我们可以利用 $\text{abc}$ 不断自我连接得到 $\text{abcabcabcabc}$，读入的 $\text{cabcabca}$，是它的子串。

规模与约定

对于全部的测试点，保证 $1<L\le 10^6$。

解题思路

本体的结论为$ans=n-nxt[n]$
如何理解？
对于例子$abcabcabcabc$，其nxt值为$00012345$，后面的值是连续的，说明循环节在不断重复。循环节的最小长度，也即是$n-nxt[n]$。
如果$nxt$值为$00012345345$，这种不是一直连续的情况，则说明到后面一个地方循环节的最小长度被迫增长，i但依然是$n-nxt[n]$。
对于串而言，随着考虑到的长度增加其循环节的长度只可能不变或者变大，对于其中某一位而言其循环节长度为$i-nxt[i]$,那对于整个串而言就是$n-nxt[n]$。

code

#include<iostream>
using namespace std;
#define MAX_N 1000000
int _next[MAX_N+5];
int l;
string s;
void get_next()
{int j=-1;_next[0]=-1;for(int i=1;s[i];i++){while(j!=-1&&s[i]!=s[j+1])j=_next[j];if(s[i]==s[j+1])j+=1;_next[i]=j;}return ;
}
int main()
{cin>>l;cin>>s;int l=s.size();get_next();cout<<l-_next[l-1]-1;return 0;
}

[POI2006] OKR-Periods of Words

题面翻译

对于一个仅含小写字母的字符串 $a$，$p$ 为 $a$ 的前缀且 $p\ne a$，那么我们称 $p$ 为 $a$ 的 proper 前缀。

规定字符串 $Q$ 表示 $a$ 的周期，当且仅当 $Q$ 是 $a$ 的 proper 前缀且 $a$ 是 $Q+Q$ 的前缀。若这样的字符串不存在，则 $a$ 的周期为空串。

例如 ab 是 abab 的一个周期，因为 ab 是 abab 的 proper 前缀，且 abab 是 ab+ab 的前缀。

求给定字符串所有前缀的最大周期长度之和。

题目描述

A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of 0 letters. By A=BC we denotes that A is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings B and C (in this order). A string P is a prefix of the string !, if there is a string B, that A=PB. In other words, prefixes of A are the initial fragments of A. In addition, if P!=A and P is not an empty string, we say, that P is a proper prefix of A.

A string Q is a period of Q, if Q is a proper prefix of A and A is a prefix (not necessarily a proper one) of the string QQ. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string A is the longest of its periods or the empty string, if A doesn’t have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.

Task Write a programme that:

reads from the standard input the string’s length and the string itself,calculates the sum of lengths of maximum periods of all its prefixes,writes the result to the standard output.

输入格式

In the first line of the standard input there is one integer $k$ ($1\le k\le 1000000$) - the length of the string. In the following line a sequence of exactly $k$ lower-case letters of the English alphabet is written - the string.

输出格式

In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input.

样例 #1

样例输入 #1

8
babababa

样例输出 #1

24

解题思路

将本问题进行等价转换，考虑求一个串的最短前后缀长度$short$，$n-short$的值就是一个串的最长前缀长度。对于$short$的求法可以递归$nxt$得到第一个不等于$0$的位置，但是时间复杂度较高，需要考虑优化，优化的思路为更新每一次遍历到的$nxt[i]$的值,即记忆化。

code

#include<iostream>
using namespace std;
#define MAX_K 1000000
char s[MAX_K+5];
int _next[MAX_K+5];
int k;
void get_next()
{int j=0;_next[1]=0;for(int i=2;i<=k;i++){while(j&&s[i]!=s[j+1])j=_next[j];if(s[i]==s[j+1])j+=1;_next[i]=j;}for(int i=2;i<=k;i++)while(_next[i]&&_next[_next[i]])_next[i]=_next[_next[i]];return ;
}
int main()
{cin>>k>>(s+1);get_next();long long ans=0;for(int i=1;i<=k;i++)if(_next[i])ans+=(i-_next[i]);cout<<ans;return 0;
}

[USACO15FEB] Censoring S

题面翻译

Farmer John为他的奶牛们订阅了Good Hooveskeeping杂志，因此他们在谷仓等待挤奶期间，可以有足够的文章可供阅读。不幸的是，最新一期的文章包含一篇关于如何烹制完美牛排的不恰当的文章，FJ不愿让他的奶牛们看到这些内容。

FJ已经根据杂志的所有文字，创建了一个字符串 $S$ ( $S$ 的长度保证不超过 $10^6$ )，他想删除其中的子串 $T$ ,他将删去 $S$ 中第一次出现的子串 $T$ ，然后不断重复这一过程，直到 $S$ 中不存在子串 $T$ 。

注意：每次删除一个子串后，可能会出现一个新的子串 $T$ （说白了就是删除之后，两端的字符串有可能会拼接出来一个新的子串 $T$ ）。

输入格式：第一行是字符串 $S$ ，第二行输入字符串 $T$ ，保证 $S$ 的长度大于等于 $T$ 的长度， $S$ 和 $T$ 都只由小写字母组成。

输出格式：输出经过处理后的字符串，保证处理后的字符串不会为空串。

Translated by @StudyingFather

题目描述

Farmer John has purchased a subscription to Good Hooveskeeping magazine for his cows, so they have plenty of material to read while waiting around in the barn during milking sessions. Unfortunately, the latest issue contains a rather inappropriate article on how to cook the perfect steak, which FJ would rather his cows not see (clearly, the magazine is in need of better editorial oversight).

FJ has taken all of the text from the magazine to create the string $S$ of length at most 10^6 characters. From this, he would like to remove occurrences of a substring $T$ to censor the inappropriate content. To do this, Farmer John finds the first occurrence of $T$ in $S$ and deletes it. He then repeats the process again, deleting the first occurrence of $T$ again, continuing until there are no more occurrences of $T$ in $S$. Note that the deletion of one occurrence might create a new occurrence of $T$ that didn’t exist before.

Please help FJ determine the final contents of $S$ after censoring is complete.

输入格式

The first line will contain $S$. The second line will contain $T$. The length of $T$ will be at most that of $S$, and all characters of $S$ and $T$ will be lower-case alphabet characters (in the range a…z).

输出格式

The string $S$ after all deletions are complete. It is guaranteed that $S$ will not become empty during the deletion process.

样例 #1

样例输入 #1

whatthemomooofun
moo

样例输出 #1

whatthefun

解题思路

本题的求解结合KMP与栈。首先从前往后进行匹配，匹配到的下标加入到栈st中，top++，一旦发现匹配成功，则top-=len2，同时j跳转到f[st[top]] (f记录对于s1当前位置可以匹配到的s2的长度)。

code

#include<iostream>
#include<cstring>
using namespace std;
#define MAX_N 1000000
char s1[MAX_N+5],s2[MAX_N+5];
int len1,len2;
int top=0;
int nxt[MAX_N+5];
int f[MAX_N+5];
int st[MAX_N+5];
void get_next()
{int j=0;for(int i=2;i<=len2;i++){while(j&&s2[i]!=s2[j+1])j=nxt[j];if(s2[i]==s2[j+1])j+=1;nxt[i]=j;}return ;
}
void KMP()
{int j=0;for(int i=1;i<=len1;i++){while(j&&s1[i]!=s2[j+1])j=nxt[j];if(s1[i]==s2[j+1])j+=1;f[i]=j;st[++top]=i;if(s2[j+1]==0)top-=len2,j=f[st[top]];}return ;
}
int main()
{cin>>(s1+1)>>(s2+1);len1=strlen(s1+1),len2=strlen(s2+1);get_next();KMP();for(int i=1;i<=top;i++)cout<<s1[st[i]];return 0;} 

[NOI2014] 动物园

题目描述

近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。

某天，园长给动物们讲解 KMP 算法。

园长：“对于一个字符串 $S$，它的长度为 $L$。我们可以在 $O(L)$ 的时间内，求出一个名为 $\mathrm{next}$ 的数组。有谁预习了 $\mathrm{next}$ 数组的含义吗？”

熊猫：“对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作 $\mathrm{next}[i]$。”

园长：“非常好！那你能举个例子吗？”

熊猫：“例 $S$ 为 $\text{abcababc}$，则 $\mathrm{next}[5]=2$。因为$S$的前$5$个字符为 $\text{abcab}$，$\text{ab}$ 既是它的后缀又是它的前缀，并且找不到一个更长的字符串满足这个性质。同理，还可得出 $\mathrm{next}[1]=\mathrm{next}[2]=\mathrm{next}[3]=0$，$\mathrm{next}[4]=\mathrm{next}[6]=1$，$\mathrm{next}[7]=2$，$\mathrm{next}[8]=3$。”

园长表扬了认真预习的熊猫同学。随后，他详细讲解了如何在 $O(L)$ 的时间内求出 $\mathrm{next}$ 数组。

下课前，园长提出了一个问题：“KMP 算法只能求出 $\mathrm{next}$ 数组。我现在希望求出一个更强大 $\mathrm{num}$ 数组一一对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 $\mathrm{num}[i]$。例如 $S$ 为 $\text{aaaaa}$，则 $\mathrm{num}[4]=2$。这是因为$S$的前 $4$ 个字符为 $\text{aaaa}$，其中 $\text{a}$ 和 $\text{aa}$ 都满足性质‘既是后缀又是前缀’，同时保证这个后缀与这个前缀不重叠。而 $\text{aaa}$ 虽然满足性质‘既是后缀又是前缀’，但遗憾的是这个后缀与这个前缀重叠了，所以不能计算在内。同理，$\mathrm{num}[1]=0,\mathrm{num}[2]=\mathrm{num}[3]=1,\mathrm{num}[5]=2$。”

最后，园长给出了奖励条件，第一个做对的同学奖励巧克力一盒。听了这句话，睡了一节课的企鹅立刻就醒过来了！但企鹅并不会做这道题，于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出$\mathrm{num}$数组呢？

特别地，为了避免大量的输出，你不需要输出 $\mathrm{num}[i]$ 分别是多少，你只需要输出所有 $(\mathrm{num}[i]+1)$ 的乘积，对 $10^9+7$ 取模的结果即可。

输入格式

第 $1$ 行仅包含一个正整数 $n$，表示测试数据的组数。
随后 $n$ 行，每行描述一组测试数据。每组测试数据仅含有一个字符串 $S$，$S$ 的定义详见题目描述。数据保证 $S$ 中仅含小写字母。输入文件中不会包含多余的空行，行末不会存在多余的空格。

输出格式

包含 $n$ 行，每行描述一组测试数据的答案，答案的顺序应与输入数据的顺序保持一致。对于每组测试数据，仅需要输出一个整数，表示这组测试数据的答案对 $10^9+7$ 取模的结果。输出文件中不应包含多余的空行。

样例 #1

样例输入 #1

3
aaaaa
ab
abcababc

样例输出 #1

36
1
32

提示

测试点编号	约定
1	$n\le 5,L\le 50$
2	$n\le 5,L\le 200$
3	$n\le 5,L\le 200$
4	$n\le 5,L\le 10,000$
5	$n\le 5,L\le 10,000$
6	$n\le 5,L\le 100,000$
7	$n\le 5,L\le 200,000$
8	$n\le 5,L\le 500,000$
9	$n\le 5,L\le 1,000,000$
10	$n\le 5,L\le 1,000,000$

解题思路

本题的本质就是求从一个位置i开始向前找其nxt[i]的值，一直找到0位置能够找到的小于i/2的位置的数量有多少。考虑递归nxt求解，但是复杂度过高，所以考虑优化。优化的思路是对于每一位的求解保证j的位置不变，一旦出现j>i/2则让j=nxt[j]，可以做到每次最多执行一次，因此复杂度为O(n)。

code

#include<iostream>
#include<cstring>
using namespace std;
#define MAX_N 1000000
#define mod 1000000007
int n;
int _next[MAX_N+5],num[MAX_N+5];
long long ans;
char s[MAX_N+5];
int t;
void get_next()
{int j=0;for(int i=2;i<=n;i++){while(j&&s[i]!=s[j+1])j=_next[j];if(s[i]==s[j+1])j+=1;_next[i]=j;num[i]=num[j]+1;}return ;
}
void get_num()
{int j=0;for(int i=2;i<=n;i++){while(j&&s[i]!=s[j+1])j=_next[j];if(s[i]==s[j+1])j+=1;while((j<<1)>i)j=_next[j];ans=(ans*(long long)(num[j]+1))%mod;}return ;
}
void solve()
{ans=1,num[1]=1;cin>>(s+1);n=strlen(s+1);get_next();get_num();cout<<ans<<endl;return ;
}
int main()
{cin>>t;while(t--)solve();return 0;
}