BZOJ3670: [Noi2014]动物园(KMP)
BZOJ3670: [Noi2014]动物园(KMP)
attack
发布于 2018-08-01 11:23:38
发布于 2018-08-01 11:23:38
题意
给出一个字符串，定义$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
*/本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-07-31 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录