首页 > > 程序设计 > C/C++ >

BZOJ3670: [Noi2014]动物园(KMP)

2018-08-02 05:43:55来源：博客园阅读 ()

题意

给出一个字符串，定义$num[i]$表示在$[1, i]$区间内互不重复的相同前后缀的数量。

最终输出$\prod_{i = 1}^n (num[i] + 1)$

Sol

去年这个时候做的题今年还是做不出来

不难看出这题应该要魔改KMP

比较烦的一个地方是要求互不重叠，我们可以先考虑求出有重叠的情况。

如果对KMP理解的比较透彻的话不难看出$num$数组是可以递推的。

具体来说是这样的(图片来自这位大佬)

然后暴力跳到一个$j < i / 2$的位置统计答案就行了。

注意不能同时跳，会T飞。。

#include<cstdio>
#include<queue>
#include<cstring>
#include<cstdlib>
#define LL long long 
using namespace std;
const int MAXN = 1e6 + 10, mod = 1e9 + 7;
char s[MAXN];
LL g[MAXN];
int nxt[MAXN];
void insert(char *s) {
    int N = strlen(s + 1); g[1] = 1;
    for(int i = 2, j = 0; i <= N; i++) {
        while(s[i] != s[j + 1] && j) j = nxt[j];
        if(s[i] == s[j + 1]) j++;
        g[i] += g[j] + 1;
        nxt[i] = j;
    }
    LL ans = 1;
    for(int i = 1, j = 0; i <= N; i++) {
        while(s[i] != s[j + 1] && j) j = nxt[j];
        if(s[i] == s[j + 1]) j++;
        while(j > i / 2 && j) j = nxt[j];
        ans = ans * 1ll * (g[j] + 1) % mod;
    }
    printf("%lld\n", ans);
}
int main() {
    int QwQ;
    scanf("%d", &QwQ);
    while(QwQ--) {
        memset(nxt, 0, sizeof(nxt));
        memset(g, 0, sizeof(g));
        scanf("%s", s + 1), insert(s);
    }
    return 0;
} 
/*
3
011
11 

*/