C++怎么实现一个后缀自动机(SAM)_C++处理所有子串问题的强大字符串数据结构

struct State { int len, link; map trans; long long cnt; // 表示到达该状态的路径数（可用于统计子串数量） State() : len(0), link(-1), cnt(0) {} };

vector st; int last = 0;

void sam_init() { st.clear(); st.push_back(State()); last = 0; }

void sam_extend(char c) { int cur = st.size(); st.push_back(State()); st[cur].len = st[last].len + 1; int p = last;

while (p != -1 && !st[p].trans.count(c)) {
    st[p].trans[c] = cur;
    p = st[p].link;
}

if (p == -1) {
    st[cur].link = 0;
} else {
    int q = st[p].trans[c];
    if (st[p].len + 1 == st[q].len) {
        st[cur].link = q;
    } else {
        int clone = st.size();
        st.push_back(st[q]);         // 复制 q 状态
        st[clone].len = st[p].len + 1;
        while (p != -1 && st[p].trans[c] == q) {
            st[p].trans[c] = clone;
            p = st[p].link;
        }
        st[q].link = clone;
        st[cur].link = clone;
    }
}
last = cur;

}

常见应用与操作
SAM 构建完成后可以解决多种问题：

  
不同子串个数：从初始状态出发，每条路径对应唯一子串。可用 DP 计算：f[u] = 1 + Σ f[v]（v 是 u 的转移目标）
  
每个子串出现次数：对每个状态标记是否为终止状态（出现在原串结尾），然后沿后缀链接反向传播计数
  
最长公共子串（两个串）：在 SAM 上匹配第二个串，维护当前匹配长度和状态，不断通过后缀链接调整


例如统计不同子串总数：
```cpp
long long count_distinct_substrings() {
    long long total = 0;
    for (int i = 1; i < st.size(); i++) {
        total += st[i].len - st[st[i].link].len;
    }
    return total;
}

基本上就这些。掌握 SAM 关键在于理解状态含义和分裂条件。实现时注意 map 可换成数组（仅限小字符集），提升性能。