您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 2406 Power Strings - KMP 算法求字符串最大循環次數

編輯：關於C++

問題描述

給定字符串 s，定義冪運算 a^n 為字符串 a 重複 n 次。求最大的 n，使得 s = a^n 對某個字符串 a 成立。字符串長度 ≤ 1,000,000。

範例：

輸入:  abcd      aaaa      ababab
輸出:  1         4         3

核心洞察：KMP Next 陣列

設字符串長度為 L，next[L] 為最長真前綴同時也是後綴的長度。若 L % (L - next[L]) == 0，則字符串由長度為 L - next[L] 的子串循環構成，答案為 L / (L - next[L])；否則答案為 1。

KMP Next 陣列構建

void getNext(const string& s, vector& next) {
    int n = s.length();
    next.resize(n + 1);
    next[0] = -1;
    int i = 0, j = -1;
    while (i < n) {
        if (j == -1 || s[i] == s[j]) {
            next[++i] = ++j;
        } else {
            j = next[j];
        }
    }
}

完整解題代碼

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 1000010;
char s[MAXN];
int nxt[MAXN];

void getNext(int len) {
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < len) {
        if (j == -1 || s[i] == s[j]) nxt[++i] = ++j;
        else j = nxt[j];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    while (scanf("%s", s) == 1) {
        if (s[0] == '.') break;
        int len = strlen(s);
        getNext(len);
        int period = len - nxt[len];
        if (len % period == 0) 
            printf("%d\n", len / period);
        else 
            printf("1\n");
    }
    return 0;
}