[bzoj 3670]NOI 2014動物園変形KMP

接頭辞を定義します.この接頭辞は接尾辞と同じで交差していません.num[i]は前のiビットにこのような接頭辞がいくつあるかです.

5.【NOI 2014】動物園

最近、園長は動物園の中で怠け者の動物が増えていることを発見した.例えばペンギンは、萌えが観光客に食べられるものしか売っていません.動物園の悪風を治すために、動物たちが自分の才能で観光客に食べなければならない園長にアルゴリズムクラスを開設し、動物たちにアルゴリズムを学ぶことにした.ある日、園長は動物たちにKMPアルゴリズムを説明した.
園長:「文字列SSの長さはLLです.O(L)O(L)の時間内にnextという配列を求めることができます.next配列の意味を予習した人はいますか?」
パンダ:「文字列SSの前ii文字からなるサブストリングは、その接尾辞であり、その接頭辞である文字列のうち、それ自体を除き、最長の長さをnext[i]と記す.」
園長:「とてもいいですね.例を挙げてもらえますか.」
パンダ:「例えばSSがabcababcであればnext[5]=2.Sの最初の5文字はabcabであり、abはその接尾辞であり接頭辞であり、この性質を満たす長い文字列が見つからないからである.同様に、next[1]=next[2]=next[3]=0、next[4]=next[6]=1、next[7]=2、next[8]=3も得られる.」
園長はまじめに予習したパンダの同級生をほめた.その後,O(L)O(L)の時間内にnext配列を求める方法を詳細に説明した.授業が終わる前に、園長は「KMPアルゴリズムではnext配列しか求められない.文字列SSの前ii文字からなるサブストリングについて、その接尾辞でありながらその接頭辞であり、その接頭辞とは重ならないより強力なnum配列を求めたい.この文字列の数をnum[i]と記す.例えばSSがaaaaaであればnum[4]=2.これは、SSの最初の44文字がaaaaであり、aとaaはいずれも「接尾辞であり接頭辞である」性質を満たし、この接尾辞がこの接頭辞と重複しないことを保証するためである.aaaは「接尾辞であり接頭辞である」という性質を満たしているが.しかし残念ながらこの接尾辞はこの接頭辞と重なっているので計算に入れません.同様にnum[1]=0,num[2]=num[3]=1,num[5]=2である.」
最後に、園長は奨励条件を提供し、最初に正しい同級生にチョコレートを1箱奨励した.それを聞いて、授業中に寝ていたペンギンはすぐに目が覚めました.しかし、ペンギンはこの問題をしないので、動物園を見学しているあなたに助けを求めました.ペンギンがnum配列を求めるプログラムを書くのを手伝ってもらえますか?
特に、大量の出力を避けるためにnum[i]をそれぞれいくら出力する必要はなく、∏Li=1(num[i]+1)∏i=1 L(num[i]+1)を100000071000000007に対して型を取った結果を出力するだけでよい.
ここで∏ni=1(num[i]+1)=(num[1]+1)×(num[2]+1)×⋯×(num[n]+1)∏i=1n(num[i]+1)=(num[1]+1)×(num[2]+1)×⋯×(num[n]+1). 入力フォーマット
入力ファイルの1行目には正の整数nnが1つしか含まれていません
テストデータのグループ数を表します.その後nn行、各行はテストデータのセットを記述する.
各テストデータのセットには1文字列SSのみが含まれており、SSの定義の詳細はタイトルの説明を参照してください.データはSSを保証し、中には小文字しか含まれていない.入力ファイルには余分な空白行は含まれず、行末に余分なスペースは存在しません.出力フォーマット
出力ファイルにnn行を含める
各行は、テストデータのセットの答えを説明します.
答えの順序は入力データの順序と一致しなければならない.各テストデータのセットについて、1つの整数を出力する必要があります.このテストデータのセットの答えが100000007型を取った結果を示します.
出力ファイルに余分な空行サンプルを含めるべきではありませんinput
3 aaaaa ab abcababc
output
36 1 32
Solution: 1.Nex[]2変解を繰り返さない;(2回目jは前回に続いて複雑度が減った!)2.num[]は個数であり、繰返し可能である.eg:元のnex[]のnum[i]=num[nex[i]+1;num[i]にはnum[nex[i]の部分があるに違いないので、もう一つ追加します.

#include<iostream> #include<stdio.h> #include<string.h> using namespace std; char s[1000005]; int T; long long ans=1; int len=0; const int MOD=1000000007; int nex[1000005]; int num[1000005]; inline void kmp1(char s[]) { // int j=-1; // nex[0]=-1; // int len=strlen(s); // for(int i=0;i<len;i++) // { // while(j!=-1&&s[j+1]!=s[i]) j=nex[j]; // if(s[i]==s[j+1]&&i!=0) j++; // nex[i]=j; // } num[1]=1; int j=0; for(int i=2;s[i];i++) { while(j!=0&&s[i]!=s[j+1]) j=nex[j]; if(s[i]==s[j+1]) j++; num[i]=num[j]+1; nex[i]=j; } // for(int i=1;i<=len;i++) cout<<num[i]<<" "; // cout<<endl; } inline void kmp2(char s[]) { int j=0; for(int i=2;s[i];i++) { // int j=nex[i]; // while(j*2>i&&j!=0) j=nex[j]; while(j!=0&&s[i]!=s[j+1]) j=nex[j]; if(s[i]==s[j+1]) j++; while(j*2>i) j=nex[j]; // num[i]=num[j]; // cout<<j<<" "<<num[j]<<endl; ans=ans*(num[j]+1)%MOD; } } int main() { scanf("%d",&T); for(int i=1;i<=T;i++) { scanf("%s",s+1); ans=1; kmp1(s); kmp2(s); // for(int i=1;i<=len;i++) cout<<num[i]<<" ";  printf("%lld
",ans); } }