首页 > 代码库 > Luogu P2375 动物园 kmp
Luogu P2375 动物园 kmp
P2375 动物园
题目描述
近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。
某天，园长给动物们讲解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]分别是多少，你只需要输出所有num[i]的乘积，对1,000,000,007取模的结果即可。
输入输出格式
输入格式：第1行仅包含一个正整数n ，表示测试数据的组数。随后n行，每行描述一组测试数据。每组测试数据仅含有一个字符串S，S的定义详见题目描述。数据保证S 中仅含小写字母。输入文件中不会包含多余的空行，行末不会存在多余的空格。
输出格式：包含 n 行，每行描述一组测试数据的答案，答案的顺序应与输入数据的顺序保持一致。对于每组测试数据，仅需要输出一个整数，表示这组测试数据的答案对 1,000,000,007 取模的结果。输出文件中不应包含多余的空行。
输入输出样例
3aaaaaababcababc
36132
说明
测试点编号 约定
1 N ≤ 5, L ≤ 50
2 N ≤ 5, L ≤ 200
3 N ≤ 5, L ≤ 200
4 N ≤ 5, L ≤ 10,000
5 N ≤ 5, L ≤ 10,000
6 N ≤ 5, L ≤ 100,000
7 N ≤ 5, L ≤ 200,000
8 N ≤ 5, L ≤ 500,000
9 N ≤ 5, L ≤ 1,000,000
10 N ≤ 5, L ≤ 1,000,000
Solution
Pre.
首先呢，这是一道非常好的语文题兼OI题。。
表示看题目时先是将num[i]看成了(前i个字符组成的字符串)的(最长的满足(既是它的后缀同时又是它的前缀)而且(不重叠)的子串长度)
然后沙茶地认为前next[i]*2>i时，num[i]=i div 2;【捂脸熊.....】
于是发现样例的奇怪
于是又看了下题目，结果又是把num[i]看成(s的子串中)(最长的满足(既是它的后缀同时又是它的前缀)而且(不重叠)的子串长度)=i的个数【泪奔.....】
好吧，题意其实很清楚，怪我没认真看题。。。。
“对于字符串S的前i个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]"
Sol.
感谢 @ 某沙茶的OI代码库 写的题解，主要思路[应用部分]来自[省选前题目整理][BZOJ 3670][NOI 2014]动物园(KMP)
我们可以先用kmp求出$next$数组
然后我们构造一个$cnt$数组，
//注意：前缀$i$指的是前i个字符组成的字符串
$cnt[i]$=为满足既是前缀$i$的前缀，又是前缀$i$的后缀的子串个数(包括前缀$i$本身)，这个数组可以通过递推在$O(n)$时间内得出：
$cnt[1]=1$ //前缀1只有本身
$cnt[i]=cnt[next[i]]+1 (1<i<=len)$ //前缀i的最长匹配next[i]+他自身
然后我们可以通过$cnt[]$和$next[]$数组求得$num[]$数组。
具体做法是，对于每个$i>=2$($i=1$时显然$num[i]=0$)，
通过沿着$next[]$指针向前走找到最大的j,
$j$满足前缀$j$既是前缀i的前缀，也是它的后缀，且$2j<=i$(即题面中所限制的前缀和后缀不重叠)，
那么$num[i]=cnt[j]$.
胡弄一番证明——:
∵当前缀$i$的前缀$j$和他长度为$j$的后缀不重叠
∴前缀$j$的长度为$u$后缀=前缀$i$的长度为$u$的后缀 //当1<=u<=cnt[j]
又∵前缀$j$的长度为$u$后缀=前缀$j$的长度为$u$前缀=前缀$i$的长度为$u$的前缀
∴前缀$i$的长度为$u$的前缀=前缀$i$的长度为$u$的后缀=前缀$j$的长度为$u$前缀(这个的种数也就是cnt[j])=前缀$j$的长度为$u$后缀
又∵我们找到的j满足$2j<=i$
∴$num[i]=cnt[j]$
然后我们就得到了一个50分的做法with TLE(注意ans为int64)：
1 program no; 2 const 3 m=1000000007; 4 var 5 b:ansistring; 6 ans:int64; 7 n,p,i,j,l,num:Longint; 8 next,cnt:array[0..1000001] of longint; 9 10 procedure get_next_and_cnt;11 begin12 j:=0;13 next[1]:=0; cnt[1]:=1;14 for i:= 2 to l do15 begin16 while (j>0) and (b[j+1]<>b[i]) do j:=next[j];17 if b[j+1]=b[i] then inc(j);18 next[i]:=j; //kmp计算next19 cnt[i]:=cnt[next[i]]+1; //顺带计算cnt20 end;21 end;22 23 procedure cal;24 begin25 ans:=1;26 for i:= 2 to l do27 begin28 j:=next[i];29 while 2*j>i do j:=next[j]; //查找最大的符合条件的J30 num:=cnt[j];31 ans:=((ans mod m)*((num+1) mod m)) mod m;32 end;33 end;34 35 begin36 //assign(input,‘1.in‘); assign(output,‘1.out‘);37 reset(input); rewrite(output);38 39 readln(n);40 for p:= 1 to n do41 begin42 readln(b); l:=length(b);43 44 get_next_and_cnt();45 cal();46 47 writeln(ans);48 end;49 50 close(input); close(output);51 end.所以还是没有AC。。。。
首先我们会发现$get_next_and_cnt()$是$O(N)$明显不会时超
所以 $cal()$是罪魁祸首！
于是下面是100分的做法：
我们可以把查找最大的符合条件的J的部分改为像kmp中的一样：
while(j<>0) and (b[j+1]<>b[i]) do j:=next[j]; if(b[j+1]=b[i]) then inc(j);
我们在循环到$i$时当前的$j$是不是可以重前一次的最长的不重叠的$j$得到呢？
答案是肯定的要么小于等于上一次的$j$，要么等于上一次的$j+1$
=====
猜想：会不会是$j+2$或更大呢？
不，可以用反证法
假设第$i-1$次循环得到$j$为$j$,这次(第$i$次)最终得到的为$j+2$
那么可以发现前缀$i$的前缀$j+2$=他长度为$j+2$的后缀
那么前缀$j+2$=前缀$i$的长度为$j+2$的后缀的长度为$j+1$的前缀(结束为$i-1$)
又因为我们得到的$j+2$满足不重叠，那么$j+1$自然也不会重叠
那么我们可以得到前缀$i-1$的的最优$j$为$j+1$
这样就冲突啦，于是这是不可能的
=====
于是我们每次求$j$的操作就接近$O(1)$,那$cal()$也就接近O(n)啦！
AC Codes:
1 program no; 2 const 3 m=1000000007; 4 var 5 b:ansistring; 6 ans:int64; 7 n,p,i,j,l,num:Longint; 8 next,cnt:array[0..1000001] of longint; 9 10 procedure get_next_and_cnt;11 begin12 j:=0;13 next[1]:=0; cnt[1]:=1;14 for i:= 2 to l do15 begin16 while (j>0) and (b[j+1]<>b[i]) do j:=next[j];17 if b[j+1]=b[i] then inc(j);18 next[i]:=j;19 cnt[i]:=cnt[next[i]]+1;20 end;21 end;22 23 procedure cal;24 begin25 ans:=1;j:=0;26 for i:= 2 to l do27 begin28 while(j<>0) and (b[j+1]<>b[i]) do j:=next[j];29 if(b[j+1]=b[i]) then inc(j); //修改的地方30 while 2*j>i do j:=next[j];31 num:=cnt[j];32 ans:=((ans mod m)*((num+1) mod m)) mod m;33 end;34 end;35 36 begin37 // assign(input,‘1.in‘); assign(output,‘1.out‘);38 reset(input); rewrite(output);39 40 readln(n);41 for p:= 1 to n do42 begin43 readln(b); l:=length(b);44 45 get_next_and_cnt();46 cal();47 48 writeln(ans);49 end;50 51 close(input); close(output);52 end.
Luogu P2375 动物园 kmp