「NOI2014」动物园-KMP

给定一个字符串$S$,求出$num$数组——对于字符串$S$的前$i$个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作$num[i]$。

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

链接

Luogu P2375

BZOJ 3670

题解

终于开始怼字符串的题了。

这一道题让我们求$num$的个数,其实联系一下AC自动机,很容易就想到沿着$nex$数组往回跳。跳的次数就是相同前后缀的个数,这个可以在求$nex$的时候直接预处理出来,记为$cnt$数组。

但题目中有一个限制比较烦人:

该后缀与该前缀不重叠

一个简单的想法就是求出$nex$数组,对于每一个$i$,先将$nex$降到$\frac{i}{2}$以下,然后看这个$nex$还能跳多少次。但是很遗憾,这个TLE了,只有$50$分。因为每一次都跳$nex$代价太高,gg


一个简单的改进就可以过掉这道题。

我们只需要像跳普通的$nex$一样去跳这个地方的$nex$,只需要每次确保其在$\frac{i}{2}$以下就可以。然后就可以找到$nex$,从而得到$num$。

说长度在$\frac{i}{2}$以下其实不太严谨,具体看代码吧。

代码

  • AC代码:
点击切换显示状态
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
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;

const int MAXN = 1110000;

int n,p = 1000000007;
int nex[MAXN],cnt[MAXN];
char s[MAXN];

void cal(){
memset(nex,0,sizeof(nex));
memset(cnt,0,sizeof(cnt));
nex[0] = 0;
int len = strlen(s);
int j = 0;
for(int i = 1;i<len;i++){
while(j > 0 && s[i]!=s[j])
j = nex[j-1];
if(s[i] == s[j]) ++j;
nex[i] = j;
cnt[i] = cnt[nex[i-1]]+1;
}
ll ans = 1;
j = 0;
for(int i = 1;i<len;i++){
while(j > 0 && s[i]!=s[j])
j = nex[j-1];
if(s[i] == s[j]) ++j;
while(j>0 && 2*j > i+1)
j = nex[j-1];
ans *= (cnt[j]+1),ans%=p;
}
printf("%lld\n",ans);
}

void solve(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%s",s);
cal();
}
}

int main(){
solve();
return 0;
}
  • 另附50分代码:
点击切换显示状态
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
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;

const int MAXN = 1110000;

int n,p = 1000000007;
int nex[MAXN],cnt[MAXN];
char s[MAXN];

void cal(){
memset(nex,0,sizeof(nex));
memset(cnt,0,sizeof(cnt));
nex[0] = 0;
int j = 0,len = strlen(s);
ll ans = 1;
for(int i = 1;i<len;i++){
while(j > 0 && s[i]!=s[j])
j = nex[j-1];
if(s[i] == s[j]) ++j;
nex[i] = j;
cnt[i] = cnt[nex[i-1]]+1;
}
for(int i = 1;i<len;i++){
j = nex[i];
while(j>0 && 2*j > i+1)
j = nex[j-1];
ans *= (cnt[j]+1),ans%=p;
}
printf("%lld\n",ans);
}

void solve(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%s",s);
cal();
}
}

int main(){
solve();
return 0;
}