第一次做NOI的题。。。。
如果知道扩展KMP的话。。。。就是水题了。。。。
#5. 【NOI2014】动物园
近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的园长决定开设算法班，让动物们学习算法。 某天，园长给动物们讲解KMP算法。
园长：“对于一个字符串
熊猫：“对于字符串
next[i]。”
园长:“非常好,那你能举个例子吗?”
熊猫:“例如
next[1] = next[2] = next[3] = 0, next[4] = next[6] = 1, next[7] = 2, next[8] = 3。”
园长表扬了认真预习的熊猫同学。随后，他详细讲解了如何在
最后，园长给出了奖励条件，第一个做对的同学奖励巧克力一盒。听了这句话，睡了一节课的企鹅立刻就醒过来了。但企鹅并不会做这道题，于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出num数组呢？
特别地，为了避免大量的输出，你不需要输出num[i]分别是多少，你只需要输出
其中
输入格式
输入文件的第1行仅包含一个正整数
表示测试数据的组数。 随后
每组测试数据仅含有一个字符串
输出格式
输出文件应包含
每行描述一组测试数据的答案
答案的顺序应与输入数据的顺序保持一致。对于每组测试数据，仅需要输出一个整数，表示这组测试数据的答案对1000000007取模的结果。
输出文件中不应包含多余的空行
样例一
input
3 aaaaa ab abcababc
output
36 1 32
样例二
见“样例数据下载”
限制与约定
| 测试点编号 | 约定 |
|---|---|
| 1 |
|
| 2 |
|
| 3 |
|
| 4 |
|
| 5 |
|
| 6 |
|
| 7 |
|
| 8 |
|
| 9 |
|
| 10 |
|
时间限制：
空间限制：
下载
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long int LL;
const int maxn=1001000;
const LL MOD=1000000007;
char P[maxn];
int next[maxn],n;
void pre_exkmp(char P[])
{
int m=strlen(P);
next[0]=m;
int j=0,k=1;
while(j+1<m&&P[j]==P[j+1])j++;
next[1]=j;
for(int i=2;i<m;i++)
{
int p=next[k]+k-1;
int L=next[i-k];
if(i+L<p+1) next[i]=L;
else
{
j=max(0,p-i+1);
while(i+j<m&&P[i+j]==P[j]) j++;
next[i]=j; k=i;
}
}
}
int xxx[maxn];
int main()
{
int T_T;
scanf("%d",&T_T);
while(T_T--)
{
memset(xxx,0,sizeof(xxx));
memset(next,0,sizeof(next));
scanf("%s",P);
n=strlen(P);
pre_exkmp(P);
for(int i=1;i<n;i++)
{
if(next[i])
{
xxx[i]++;
int t1=i+next[i];
int t2=2*i;
xxx[min(t1,t2)]--;
}
next[i]=0;
}
LL ans=1;
LL now=0;
for(int i=0;i<n;i++)
{
now+=xxx[i];
ans=(ans*(now+1))%MOD;
}
cout<<ans<<endl;
}
return 0;
}