FZU 1901 Period II（KMP中的next）題解

題意：給你一串字元串，問你前字尾相同情況有幾種，并輸出字尾位置（？這裡一直沒看懂length是什麼，但是這樣了解答案也對，然後還要加上本身長度）

思路：這裡好好講講next的用法。我們都知道next代表前字尾比對值，現在我們以下面這個字元串為例，講述next的用法：

len = 9,next[len] = 4，所我們找到了第一個前字尾比對串abab，next[ next[len] ] = next[4] = 2，是以第二個前字尾比對串長度為2。因為next[len] = 4，是以s[0...3] == s[5...8]，而next[4] = 2，即s[01] == s[23] == s[89]，是以第二個前字尾比對串為ab。以此類推，直到next<=0。

參考

代碼：

#include<set>
#include<iostream>
#include<algorithm>
const int maxn = 1000000+5;
const int INF = 0x3f3f3f3f;
using namespace std;
int fail[maxn],ans[maxn];
char s[maxn];
void getFail(char *p,int len){
     fail[0] = -1;
     int j = 0,k = -1;
     //int len = strlen(p);
     while(j < len){
        if(k == -1 || p[j] == p[k]){
            fail[++j] = ++k;
        }
        else{
            k = fail[k];
        }
     }
}

int main(){
    int T,Case = 1;
    scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        int len = strlen(s);
        getFail(s,len);
        int i = len,cnt = 0;
        while(fail[i] > 0){
            ans[cnt++] = len - fail[i];
            i = fail[i];
        }
        ans[cnt++] = len;
        sort(ans,ans+cnt);
        printf("Case #%d: %d\n",Case++,cnt);
        for(int i = 0;i < cnt;i++){
            if(i != 0) printf(" ");
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}
           

轉載于:https://www.cnblogs.com/KirinSB/p/9408762.html