题目:1000.动物园
近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。
为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学习算法。
某天,园长给动物们讲解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]
分别是多少,你只需要输出
$$\Pi_{i=1}^L (\texttt{num[i]}+1)$$
对1,000,000,007取模的结果即可。
输入格式
第1行仅包含一个正整数$n$ ,表示测试数据的组数。
随后$n$行,每行描述一组测试数据。每组测试数据仅含有一个字符串S,S的定义详见题目描述。
数据保证$S$中仅含小写字母。输入文件中不会包含多余的空行,行末不会存在多余的空格。
输出格式
包含$n$行,每行描述一组测试数据的答案,答案的顺序应与输入数据的顺序保持一致。
对于每组测试数据,仅需要输出一个整数,表示这组测试数据的答案对1,000,000,007取模的结果。
输出文件中不应包含多余的空行。
输入样例:
3
aaaaa
ab
abcababc
输出样例:
36
1
32
算法
这题利用KMP得出$O(n)$的解法。
首先,不考虑前缀和后缀不重叠的情况,先考虑$S$的每一个子字符串$S[1\sim i]$所能形成的相同前后缀的数量$cnt[i]$,这个表达式是
$$cnt[i]=cnt[ne[i]]+1.$$
我们来看一个例子来说明。比如aasdaa
。很容易可以理解,cnt[2]=2
。注意,字符串本身就是一个相同长度的前缀和后缀,所以是2。我们再来看cnt[6]
。本身通过kmp能够得到ne[6]=3
,所以肯定起码一种前后缀。另外,对于aa
这个前/后缀本身,我们可以把它拆开来,再形成一组前后缀,那么又多了一个,所以cnt[6]=4
。同理,对于aaaasdaaaa
,那么cnt[10]=5
。
其次,这时候再考虑前后缀不重叠的情况。和cnt
不同的地方在于,对于cnt
来说只要一层ne[i]
的嵌套,但是在找num[i]
的时候,我们需要多次嵌套ne[i]
来找到一个值使得前后缀不重复。所以我们再另用一个指针k
来首先找前后缀的尺寸,然后如果有重叠的话,再利用ne
数组对前后缀的长度缩短,最后找到合适的前后缀长度,及其对应的cnt
值。
这个算法精髓的地方在于,在找num
的值的时候,也是利用了类似kmp的方式,即用ne
往回走,由此把时间复杂度控制在了$O(n)$,$n$为字符串的长度。
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10, mod=1e9+7;
ll n, ne[N], cnt[N];
char s[N];
int main() {
cin>>n;
while (n--) {
fill(cnt, cnt+N, 0);
fill(ne, ne+N, 0);
cin>>s+1;
ll res=1;
cnt[1]=1;
for (int i=2, j=0, k=0; s[i]; i++) {
while (j && s[i]!=s[j+1]) j=ne[j];
if (s[i]==s[j+1]) j++;
ne[i]=j;
cnt[i]=cnt[j]+1;
while (k && s[i]!=s[k+1]) k=ne[k];
if (s[i]==s[k+1]) k++;
while (k<<1>i) k=ne[k];
res=res*(cnt[k]+1)%mod;
}
cout<<res<<'\n';
}
}
ne[6] = 2吧
我感觉也是