bzoj3670 Noi2014动物园 - exkmp

本文主要是介绍bzoj3670 Noi2014动物园 - exkmp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3670

题意：求出一个num数组一一对于字符串S的前i个字符构成的子串T，有字符串既是T的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]。求对1,000,000,007的取模

题解：不会kmp的我用exkmp做了。。求出的extend[]就是下面代码的nt[]，它表示字符串S与自己的后缀的匹配长度。可以发现，对每次的成功的匹配，它对num[i]-num[i+min(i-1,nt[i])都有1的贡献（注意求的是数量啊喂为此WA了一次的菜鸡挥泪提醒）。于是搞搞弄成线性的就好啦~

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 1001000
#define Mod  1000000007int nt[maxn],num[maxn];
char s[maxn];
int mymin(int x,int y){return (x<y)?x:y;}
int mymax(int x,int y){return (x>y)?x:y;}
int main()
{int T,i,id,mx,len;long long as;scanf("%d\n",&T);while (T--){gets(s+1);len=strlen(s+1);memset(nt,0,sizeof(nt));memset(num,0,sizeof(num));id=1;mx=0;nt[1]=len;for (i=2;i<=len;i++){if (mx>i+nt[i-id+1]-1) nt[i]=nt[i-id+1];else{nt[i]=mymax(mx-i+1,0);while (i+nt[i]<=len && s[1+nt[i]]==s[i+nt[i]]) nt[i]++;if (i+nt[i]-1>mx) mx=i+nt[i]-1,id=i;}num[i]+=1;num[i+mymin(i-1,nt[i])]-=1;}as=1;for (i=2;i<=len;i++){num[i]+=num[i-1];int orz=(1+num[i])%Mod;as=(as*orz)%Mod;}printf("%lld\n",as);}return 0;
}

这篇关于bzoj3670 Noi2014动物园 - exkmp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---