KMPは最小の循環節を探します

KMPは最小の循環節を探します
 
一:kmpテンプレート:next【0】=0
#define KMP_GO(X) while(k>0 && P[k]!=X[i]) k=next[k];if(P[k]==X[i])k++
//文字列PがTに現れる回数を求める
int kmp_match(char*T,char*P){
    int n,m,next[10010],i,k,c;
    n=strlen(T);m=strlen(P);
    next[1]=k=0;
    for(i=1;i
        KMP_GO(P);
        next[i+1]=k;//ここでiは文字のインデックスを表し、対応する長さi+1
    }
    k=c=0;
    for(i=0;i
        KMP_GO(T);
        if(k==m){
            c++;
            k=next[k];
        }
    }
    return c;
}
 
 
二:KMP最小循環節、循環周期:
定理:Sの長さがlenであると仮定すると,Sには最小ループ節が存在し,ループ節の長さLはlen−next[len],サブストリングはS[0...len−next[len]−1である.
(1)lenがlen−next[len]で割り切れる場合、文字列Sは完全に循環節循環からなり、循環周期T=len/Lであることを示す.
(2)できない場合は、補完するためにアルファベットを追加する必要があります.補完する必要がある個数は、ループ個数G=L-len%L=L-(len-L)%L=L-next[len]%Lであり、ここでL=len-next[len]となります.
 
 
この定理を理解するには,まずnext配列の意味を理解する:next[i]は,前の長さiのサブ列において,接頭辞と接尾辞が等しい最大長を表す.
 
 
次に、最小サイクル・セクションとサイクルをいくつかの例で説明します.
説明の便宜上、文字列の長さをlen、ループサブ列の長さをLとする
1.
s0s1s2s3s4s5 ,next[6]=3
すなわちs 0 s 1 s 2=s 3 s 4 s 5
サイクルサブストリングはs 0 s 1 s 2,L=len−next[6]=3であり,lenによって除去できることが明らかになった.
 
2.
s0s1s2s3s4s5s6s7 ,next[8]=6
このときlen-next[8]=2、すなわちL=2
s 0 s 1 s 2 s 3 s 4 s 5=s 2 s 3 s 4 s 5 s 6 s 7
s 0 s 1=s 2 s 3,s 2 s 3=s 4 s 5,s 4 s 5=s 6 s 7が分かる
明らかにs 0 s 1はサイクルサブ列である
 
3.
s0s1s2s3s4s5s6 ,next[7]=4
このときlen-next[7]=3、すなわちL=3
s 0 s 1 s 2 s 3=s 3 s 4 s 5 s 6
s 0 s 1=s 3 s 4,s 2 s 3=s 5 s 6がわかる
従って、s 0 s 1 s 2=s 3 s 4 s 5、s 0=s 3=s 6
すなわち、3-4%3=2文字(s 1 s 2)を追加すると、得られる文字列はs 0 s 1 s 2サイクルで3回構成される
 
 
テンプレート問題hdu 3746
 
タイトル:
文字列をあげて、後ろにできるだけ少ない文字を加えて、この文字列を繰り返し列にします.
例:
abca---bcを追加し、abcabcになります
abcd---abcdを追加し、abcdabcdになります
aa---追加する必要はありません
 
分析:
古典的な最小サイクルを求めて、最小サイクルの長さを見つけます:len-next[len].総長%最小サイクルセグメント長で答えを得る

#include

#define  LL long long

#define  ULL unsigned long long

using namespace std;



const int MAXN=100010;

char s[MAXN];

int Next[MAXN];

void getNext()

{

      Next[0]=0;

      int s_len=strlen(s);

      for(int i=1,k=0;i

 
参考文献
https://www.cnblogs.com/chenxiwenruo/p/3546457.html