Fork me on GitHub

[NOI-2014] Zoo KMP模拟

发表于 | 分类于
字数统计: 269字 | 阅读时长 ≈ 1分钟

题面

BZOJ-3670

分析

不考虑题目的限制,只想一般的情况.

先通过对next数组的观察,不难得到$num(i)=num(fail(i))+1$.

考虑再维护一个前缀不与后缀重叠的,带有限制的$num’(i)$, 找一波规律得到

相当于同时维护了两个失配数组了嘛.

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
typedef long long ll;
int n;
char s[maxn];
int fail[maxn],num1[maxn],num2[maxn];
const int Mod = 1e9+7;
ll kmp(char *b)
{
    ll ans = 1;
    int nb = strlen(b+1),k = 0,t = 0;
    for (int i = 2; i <= nb; i++)
    {
        while(k && s[k+1] != s[i]) k = fail[k];
        while((t && s[t+1] != s[i]) || t >= (i>>1)) t = fail[t];
         
        if(s[t+1] == s[i]) num2[i] = num1[++t] + 1; 
        else num2[i] = 0;
        if(s[k+1] == s[i]) fail[i] = ++k,num1[i] = num1[k] + 1;
        else num1[i] = fail[i] = 0; 
        ans = (ans * (num2[i]+1)) % Mod;
    }
    return ans;
}
 
int main(int argc, char *argv[])
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",s+1);
        printf("%lld\n",kmp(s));
    }
    return 0;
}