This page looks best with JavaScript enabled

「NOI2014」动物园-KMP

 ·  ✏️ About  737 words  ·  ☕ 2 mins read · 👀... views

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

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

链接

Luogu P2375

题解

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

这一道题让我们求 $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;
}

cqqqwq
WRITTEN BY
cqqqwq
A student in Computer Science.

评论: