SDUTOJ 2475 Power Strings：KMP 求最小循環節

問題描述

給定字符串 s，求最小的 k 使得 s 由某長度為 k 的子串重複構成。即求最小循環節長度，輸出重複次數 n/k。

KMP next 數組應用

構建 next 數組（失敗函數）。設 len = s.length()。若 len % (len - next[len]) == 0，則最小循環節長度為 len - next[len]，重複次數為 len / (len - next[len])。否則為 1。

代碼

#include <iostream> #include <cstring>
#define N 1000005
int next[N]; char s[N];
void getnext(char s[]) {
    int j=-1, i=0, len=strlen(s);
    next[0]=-1;
    while (i < len) {
        if (j==-1 || s[i]==s[j]) { ++i; ++j; next[i]=j; }
        else j=next[j];
    }
}
int main() {
    while (std::cin >> s) {
        if (s[0]=='.') break;
        int len=strlen(s);
        getnext(s);
        if (len % (len - next[len]) == 0)
            std::cout << (len / (len - next[len])) << std::endl;
        else std::cout << 1 << std::endl;
    }
    return 0;
}

原理

next[len] 為最長真前綴同時也是後綴的長度。len - next[len] 即為最小周期候選。