[省選前テーマ整理][BZOJ 3670][NOI 2014]動物園(KMP)
4079 ワード
タイトルリンク
http://www.lydsy.com/JudgeOnline/problem.php?id=3670
構想
簡単に述べるために,以下に述べる接頭辞iは文字列中の区間[1,i]に対応するサブ列である.
KMP定義によれば、next[i]=jは、接頭辞jが接頭辞iである接頭辞を満たし、jが最大であることを示す.(実はタイトルにも説明があります)
次にnext[]配列に基づいてcnt[]配列を構築することができ、cnt[i]=接頭辞iである接頭辞であり、接頭辞iの接尾辞であるサブ列の個数を満たすことができ、この配列はO(n)時間内にプッシュすることによって得ることができる.
cnt[1]=1
cnt[i]=cnt[next[i]]+1
次に,cnt[]とnext[]配列からnum[]配列を得ることができる.具体的には、i>=2(i=1の場合num[i]=0)ごとにnext[]ポインタに沿って進むことで最大のjが見つかり、jがプレフィックスjを満たすのはプレフィックスiのプレフィックスであり、その接尾辞でもあり、2 j<=i(すなわち、問題面で制限されたプレフィックスと接尾辞が重ならない)ではnum[i]=cnt[j]となる.
コード#コード#
http://www.lydsy.com/JudgeOnline/problem.php?id=3670
構想
簡単に述べるために,以下に述べる接頭辞iは文字列中の区間[1,i]に対応するサブ列である.
KMP定義によれば、next[i]=jは、接頭辞jが接頭辞iである接頭辞を満たし、jが最大であることを示す.(実はタイトルにも説明があります)
次にnext[]配列に基づいてcnt[]配列を構築することができ、cnt[i]=接頭辞iである接頭辞であり、接頭辞iの接尾辞であるサブ列の個数を満たすことができ、この配列はO(n)時間内にプッシュすることによって得ることができる.
cnt[1]=1
cnt[i]=cnt[next[i]]+1
次に,cnt[]とnext[]配列からnum[]配列を得ることができる.具体的には、i>=2(i=1の場合num[i]=0)ごとにnext[]ポインタに沿って進むことで最大のjが見つかり、jがプレフィックスjを満たすのはプレフィックスiのプレフィックスであり、その接尾辞でもあり、2 j<=i(すなわち、問題面で制限されたプレフィックスと接尾辞が重ならない)ではnum[i]=cnt[j]となる.
コード#コード#
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define MAXN 1000100
#define MOD 1000000007
using namespace std;
typedef long long int LL;
LL ans=0;
char s[MAXN];
int next[MAXN],cnt[MAXN]; //cnt[i]= 1~i
void getnext(char str[],int len)
{
int k=0;
next[1]=0;
cnt[1]=1; //!!!!!!
for(int i=2;i<=len;i++)
{
while(k>0&&str[k+1]!=str[i]) k=next[k];
if(str[k+1]==str[i]) k++;
next[i]=k;
cnt[i]=cnt[k]+1;
}
}
LL work(char str[],int len)
{
int k=0;
ans=1;
for(int i=2;i<=len;i++) // next[] cnt[] num[i]
{
while(k&&str[k+1]!=str[i]) k=next[k];
if(str[k+1]==str[i]) k++;
while((k*2)>i) k=next[k];
ans=(ans*(cnt[k]+1))%MOD;
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",s+1);
int len=strlen(s+1);
getnext(s,len);
printf("%lld
",work(s,len));
}
return 0;
}