Codeforces 235C Cyclical Quest：後綴自動機解決循環同構子串查詢

問題重述

給定文本串 S (|S|≤1e6)，Q≤1e5 查詢串 x_i (∑|x_i|≤1e6)。
查詢：S 中有多少個**連續子串**與 x_i **循環同構**（循環移位後相等）。

關鍵轉化

x 的所有循環移位 = x+x 的長度 |x| 子串。
問題等價於：在 S 中統計有多少個長度為 L=|x| 的子串，出現在 x+x 中（且長度恰為 L）。

後綴自動機 (SAM) 解法

1. 對 S 構建 SAM，預計算每個狀態的 cnt（endpos 集合大小，即該狀態對應子串在 S 中出現次數）。
2. 對每個查詢串 x：
   　a. 構造 T = x + x（去掉最後一字符避免重複）。
   　b. 在 SAM 上匹配 T，維護當前匹配長度 l 和狀態 p。
   　c. 當 l == L 時，記錄狀態 p 的 cnt（去重：同一狀態只算一次）。
   　d. 繼續匹配，l 超過 L 時沿 link 跳轉縮短。

SAM 核心結構

struct State {
    int next[26], link, len, cnt, firstPos;
    State() : link(-1), len(0), cnt(0), firstPos(-1) { memset(next, -1, sizeof next); }
};
vector sam(2*MAXL);
int last = 0, sz = 1;

void samExtend(char c, int pos) {
    int cur = sz++; sam[cur].len = sam[last].len + 1; sam[cur].firstPos = pos;
    int p = last;
    while (p != -1 && sam[p].next[c] == -1) {
        sam[p].next[c] = cur; p = sam[p].link;
    }
    if (p == -1) sam[cur].link = 0;
    else {
        int q = sam[p].next[c];
        if (sam[p].len + 1 == sam[q].len) sam[cur].link = q;
        else {
            int clone = sz++; sam[clone] = sam[q];
            sam[clone].len = sam[p].len + 1; sam[clone].cnt = 0;
            while (p != -1 && sam[p].next[c] == q) {
                sam[p].next[c] = clone; p = sam[p].link;
            }
            sam[q].link = sam[cur].link = clone;
        }
    }
    last = cur;
}

出現次數計算

void calcCnt() {
    vector bucket(maxLen+1);
    for (int i=1;i order(sz);
    for (int i=1;i0;--i) {
        int v = order[i];
        if (sam[v].link != -1) sam[sam[v].link].cnt += sam[v].cnt;
    }
}

查詢匹配邏輯

int query(string x) {
    string T = x + x.substr(0, x.size()-1);
    int L = x.size();
    int ans = 0, p = 0, l = 0;
    vector vis(sz, -1);
    for (int i=0;i L) { p = sam[p].link; l = sam[p].len; }
        if (l == L && vis[p] != queryId) {
            vis[p] = queryId;
            ans += sam[p].cnt;
        }
    }
    return ans;
}

複雜度

構建 SAM O(|S|)，計算 cnt O(|S|)。
每查詢 O(|x|)，總 O(|S| + ∑|x|) 線性，完美滿足限制。