NOI2014 动物园

题目简要描述

设num[i]表示既是S[1..i]的前缀又是后缀,并且前缀和后缀不重叠的字符串个数。 求 10000000071000000007取模的结果。 10%:|S|<=50 30%:|S|<=200 50%:|S|<=10000 100%:|S|<=1000000

一些定义

设fail2[i]表示最长的符合要求的字符串长度。 设sum[i]表示既是S[1..i]的前缀又是后缀的字符串个数。(可以和S[1..i]相同)。 设fail[i]表示最长的既是S[1..i]的前缀又是后缀的并且和S[1..i]不同的字符串长度, 则sum[i]=sum[fail[i]]+1。 我们发现num[i]=sum[fail2[i]]

(大)暴力

求fail2[i]的时候根据fail指针搜。 并不知道能否获得50分。

正解水过去的方法

求fail2[i]的时候用倍增。可以水到100分。

正解

fail2和fail有着相同的性质:fail2[i]<=fail2[i-1]+1(显然) 那么直接像KMP一样就好了。 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define up(a,b,c) for (long long a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (long long a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (long long a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (long long a(b),end##a(c);a>=end##a;--a)
using namespace std;
long long read(){
char s;
long long k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9'){
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(long long x){
if(x<0){
putchar('-');
write(-x);
}
else{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
char s[2333333];
long long f[2333333],f2[2333333],num[2333333],num2[2333333];
//f[i]-->fail[i] f2[i]-->fail2[i] num[i]-->sum[i] num2[i]-->num[i]
int main(){
long long n,t,l,ln,ans;
scanf("%lld\n",&n);//多组数据
while(n){
--n;
scanf("%s\n",s+1);
ln=strlen(s+1);
t=0,l=0;ans=1;
num[1]=1;
for(int i=2;i<=ln;++i){
f[i]=f2[i]=num[i]=num2[i]=0;
while(s[t+1]!=s[i]&&t)t=f[t];
while((s[l+1]!=s[i]&&l)||i/2<=l)l=f[l];
if(s[t+1]==s[i])f[i]=++t;//47和49行是标准的KMP算法
if(s[l+1]==s[i])f2[i]=++l;
num[i]=num[f[i]]+1;
num2[i]=f2[i]?num[f2[i]]?num[f2[i]]:1:0;
ans*=num2[i]+1;
ans%=1000000007;

}
//up(i,2,ln)printf("%d %d %d %d\n",f[i],f2[i],num[i],num2[i]);
printf("%lld\n",ans);
}
return 0;
}

文章目录
  1. 1. 题目简要描述
  2. 2. 一些定义
  3. 3. (大)暴力
  4. 4. 正解水过去的方法
  5. 5. 正解
|

博客使用Disqus作为评论系统