[kuangbin带你飞]专题十六 KMP & 扩展KMP &

思路

KMP的next数组的性质。

• 最小循环节length=plen-next[len]。
• 通过是否整除判断是否完全循环

AC代码

#include<iostream>
using namespace std;
const int MAXN=10000002;

string P;
string T;

int NEXT[MAXN];
int plen,tlen;
void getNEXT(){
    NEXT[0] = -1;
    int k = -1 ;
    int j = 0 ;
    while(j<plen){
        if(k==-1||P[k]==P[j]){
            NEXT[++j] = ++k;
        }else{
            k = NEXT[k];
        }
    }
    
}

int main(){
    
    ios::sync_with_stdio(false);
    int N;
    int ccase = 1;
    while(cin>>N&&N!=0){
        cin>>P;
        plen=N;
        getNEXT();
        cout<<"Test case #"<<ccase++<<"\n";
        for(int i = 2;i<=plen;i++){
            int length = i - NEXT[i];
            if(length!=i&&i%length==0){
                cout<<i<<" "<<i/length<<"\n";
            }
        }
        cout<<"\n";
    }       
    return 0;
}