POJ 1509 Glass Beads：後綴自動機求最小循環表示

POJ 1509「Glass Beads」：給定環形字符串，求字典序最小的起始位置。本文介紹後綴自動機 (SAM) 解法：構建 SAM，從根節點貪心走最小字符邊長度 n 次，終點即為最小表示的終點。

問題轉化

• 環形字符串 S，長度 n。
• 最小循環表示 ⇔ 在 S+S 中長度為 n 的子串中字典序最小者。
• 構建 S+S 的後綴自動機，所有子串對應 SAM 中的路徑。
• 字典序最小子串 = 從根節點開始，每步選擇最小可用字符邊，走 n 步。

後綴自動機核心結構

struct State {
    State* next[26]; // 轉移
    State* link;     // 後綴鏈接
    int len;         // 最長長度
    State(int l=0) : len(l), link(nullptr) {
        memset(next, 0, sizeof(next));
    }
};

擴展函數

State* extend(State* last, int c) {
    State* cur = new State(last->len + 1);
    State* p = last;
    while (p && !p->next[c]) {
        p->next[c] = cur;
        p = p->link;
    }
    if (!p) cur->link = root;
    else {
        State* q = p->next[c];
        if (q->len == p->len + 1) cur->link = q;
        else {
            State* clone = new State(p->len + 1);
            clone->link = q->link;
            memcpy(clone->next, q->next, sizeof(q->next));
            while (p && p->next[c] == q) {
                p->next[c] = clone;
                p = p->link;
            }
            q->link = cur->link = clone;
        }
    }
    return cur;
}

查找最小循環表示

int findMinCyclic(const string& s) {
    // 建構 s+s 的 SAM
    State* root = new State(0);
    State* last = root;
    for (char ch : s) last = extend(last, ch - 'a');
    for (char ch : s) last = extend(last, ch - 'a'); // 第二遍

    // 從根貪心走 n 步
    State* cur = root;
    for (int i = 0; i < s.size(); ++i) {
        for (int c = 0; c < 26; ++c) {
            if (cur->next[c]) {
                cur = cur->next[c];
                break;
            }
        }
    }
    // cur->len 為匹配長度，起始位置 = cur->len - n + 1 (1-based)
    return cur->len - s.size() + 1;
}

完整代碼（優化內存池版）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 10010;
const int MAXS = MAXN * 2;

struct State {
    int next[26];
    int link, len;
} st[MAXS];
int sz, last;

int newState(int len) {
    st[sz].len = len;
    st[sz].link = -1;
    memset(st[sz].next, -1, sizeof(st[sz].next));
    return sz++;
}

void init() {
    sz = 0;
    last = newState(0); // root = 0
}

void extend(int c) {
    int cur = newState(st[last].len + 1);
    int p = last;
    while (p != -1 && st[p].next[c] == -1) {
        st[p].next[c] = cur;
        p = st[p].link;
    }
    if (p == -1) st[cur].link = 0;
    else {
        int q = st[p].next[c];
        if (st[q].len == st[p].len + 1) st[cur].link = q;
        else {
            int clone = newState(st[p].len + 1);
            st[clone].link = st[q].link;
            memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
            while (p != -1 && st[p].next[c] == q) {
                st[p].next[c] = clone;
                p = st[p].link;
            }
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        init();
        char s[MAXN]; scanf("%s", s);
        int n = strlen(s);
        for (int i = 0; i < n; ++i) extend(s[i] - 'a');
        for (int i = 0; i < n; ++i) extend(s[i] - 'a');
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            for (int c = 0; c < 26; ++c)
                if (st[cur].next[c] != -1) { cur = st[cur].next[c]; break; }
        }
        printf("%d\n", st[cur].len - n + 1);
    }
    return 0;
}

複雜度

• 構建 SAM：O(n) 狀態數 ≤ 2n，每次擴展攤還 O(1)。
• 查找：O(n × 字符集) = O(26n) = O(n)。
• 總時間 O(n)，空間 O(n)。

對比：最小表示法 (O(n) 雙指針)

int minCyclicString(const string& s) {
    int n = s.size(), i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        char a = s[(i+k)%n], b = s[(j+k)%n];
        if (a == b) ++k;
        else {
            if (a > b) i += k+1;
            else j += k+1;
            if (i == j) ++i;
            k = 0;
        }
    }
    return min(i, j) + 1; // 1-based
}

最小表示法更簡短、常數更小，是該問題的標準解法。SAM 解法展示了自動機在子串查詢上的通用性，適合學習 SAM 結構。

總結

本題可用最小表示法（雙指針 O(n)）或後綴自動機（構建 S+S 的 SAM，貪心走最小邊）解決。SAM 解法雖代碼較長，但展示了「構建自動機 + 字典序遍歷」的通用模式，可推廣至「字典序第 k 小子串」、「最長公共子串」等問題。學習 SAM 時建議先掌握構建邏輯，再理解其在子串集合上的導航能力。