后缀自动机的应用

求两个字符串的最长公共子串

方法：

对于 $A$ 字符串建 $SAM$ ，考虑 $B$ 串从头到尾枚举。假设枚举到第 $i$ 位。

用 $x$ 表示当前（到第 $i-1$ 位）在 $SAM$ 走到的节点， $l$ 表示当前匹配的以字符 $c$ ( $b$ 串的第 $i$ 个字符)结尾的子串中最大的长度。

若 $ch_{x,c}=0$ ,则 $x=fa_x$ 直到 $x$ 为 $0$ 。

否则， $x=ch_{x,c}$ ， $l=l+1$ 此时满足 $x$ 到根节点 $1$ 的路径上的所有点，都是合法的子串。显然最大的就是 $l$ 。跟答案取大就行了。

       int ans = 0, n = strlen(s + 1), now = 0, p = 1;
        for(int i = 1; i <= n; ++i) {
            int c = s[i] - 'a';
            if(ch[p][c]) p = ch[p][c], ++now;
            else {
                while(p && !ch[p][c]) p = fa[p];
                if(!p) now = 0;
                else now = len[p] + 1, p = ch[p][c];
            }
            ans = max(ans, now);
        }

求多个串的最长公共子串

SPOJ1812 Longest Common Substring II

方法：

对第一个串建 $SAM$ 。然后对于剩下的串，都从头到尾遍历一遍。按照前一题的思路，

假设枚举到第 $i$ 位。

用 $x$ 表示当前（到第 $i-1$ 位）在 $SAM$ 走到的节点， $l$ 表示当前匹配的以字符 $c$ ( $b$ 串的第 $i$ 个字符)结尾的子串中最大的长度。

若 $ch_{x,c}=0$ ,则 $x=fa_x$ 直到 $x$ 为 $0$ 。

否则， $x=ch_{x,c}$ ， $l=l+1$ 此时满足 $x$ 到根节点 $1$ 的路径上的所有点，都是合法的子串。

然后每个节点取子树里的最大值，然后取自己和这个最大值的最小值。

对于每个节点与答案取最小值。

memset(f, 0, sizeof f);
for(int i = 1; i <= n; ++i) {
    int c = s[i] - 'a';
    if(ch[p][c]) p = ch[p][c], ++now;
    else {
        while(p && !ch[p][c]) p = fa[p];
        if(!p) now = 0;
        else now = len[p] + 1, p = ch[p][c];
    }
    f[p] = max(f[p], now);
}    
for(int i = cnt; i >= 1; --i) {
    int q = fa[a[i]];
    f[q] = max(f[q], f[a[i]]);
    f[a[i]] = min(f[a[i]], len[a[i]]);
    g[a[i]] = min(g[a[i]], f[a[i]]);
}
int ans = 0;
for(int i = 1; i <= cnt; ++i) ans = max(ans, g[i]);

求循环同构在主串里的出现次数

CF235C Cyclical Quest

方法：

对主串 $S$ 建 $SAM$ 。

按照上面两题的思路， $x$ 表示匹配到的 $SAM$ 上的节点。

$go(c)$ 表示在当前匹配的字符串末尾加上字符 $c$

$del()$ 表示删除当前匹配的字符串的首字符

$cal()$ 计算答案。

具体细节直接看代码：

    void go(int c) {
        while(x && !ch[x][c]) l = len[x = fa[x]];
        if(ch[x][c]) {
            x = ch[x][c];
            ++l;
        }
    }
    void cal() {
        if(l == n && vis[x] < TT) {
            ans += siz[x];
            vis[x] = TT;
        }
    }
    void del() {
        if(l > n && (--l == len[fa[x]])) x = fa[x];
    }
    void solve() {
        ans = 0;
        scanf("%s", s +1);
        n = strlen(s +1);
        x = 1;
        l = 0;
        for(int i = 1; i <= n; ++i) go(s[i] - 'a');
        cal();
        for(int i = 1; i < n; ++i) {
            go(s[i] - 'a');
            del();
            cal();
        }
        printf("%d\n", ans);
    }