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 取模的结果。输出文件中不应包含多余的空行。

输入输出样例

输入样例#1：

3

aaaaa

ab

abcababc

输出样例#1：

说明

测试点编号约定

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 begin

12      j:=0;

13     next[1]:=0;  cnt[1]:=1;

14     for i:= 2 to l do

15     begin

16       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计算next

19       cnt[i]:=cnt[next[i]]+1;  //顺带计算cnt

20     end;

21 end;

22

23 procedure cal;

24 begin

25     ans:=1;

26     for i:= 2 to l do

27       begin

28           j:=next[i];

29           while 2*j>i do j:=next[j];  //查找最大的符合条件的J

30           num:=cnt[j];

31           ans:=((ans mod m)*((num+1) mod m)) mod m;

32       end;

33 end;

34

35 begin

36    //assign(input,'1.in'); assign(output,'1.out');

37    reset(input); rewrite(output);

38

39    readln(n);

40    for p:= 1 to n do

41    begin

42      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 begin

12      j:=0;

13     next[1]:=0;  cnt[1]:=1;

14     for i:= 2 to l do

15     begin

16       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 begin

25     ans:=1;j:=0;

26     for i:= 2 to l do

27       begin

28         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 begin

37   // assign(input,'1.in'); assign(output,'1.out');

38    reset(input); rewrite(output);

39

40    readln(n);

41    for p:= 1 to n do

42    begin

43      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 [NOI2014 D2]动物园 kmp