题解 P4081 【[USACO17DEC]Standing Out from the Herd】

· · 题解

广义SAM 如果你还不会SAM强烈建议看看hiho上的解释http://www.hihocoder.com/problemset/problem/1441

直接对原串做一个广义SAM，广义SAM就是能做到多字符串匹配。和普通SAM区别就是在插入一个新的字符串时，把起始位置last=1就行了。

关于如何遍历子串：建好广义SAM之后，每一个模板串都从根节点开始遍历，然后按下面的代码来可以每次都跑到这个模板串的开头到现在位置所代表的节点，然后它的这个前缀的所有子串都是它parent树上的父亲Update(x = ch[x][s[++tot]], i);Update函数：对于每一个模板串把它在SAM上的所有子串代表的节点标记一下，如果曾经没有出现过则标记为当前子串的编号,如果曾经标记过得说明子串出现在不同的两个串中即不满足“独特性”重置为-1if (vis[x] != 0) vis[x] = -1;elsevis[x] = y;

构造完成后，最后答案就是统计SAM上每个节点集合对应的串求和，节点集合对应串的个数就是mxl[i]-mxl[pre[i]]，答案就是sum[vis[i]]+=mxl[i]-mxl[pre[i]]

感谢bztMinamoto指导

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline void read(register int &x){
    x = 0; register int f = 1;
    register char c = getchar();
    while (!(c >= '0' && c <= '9')){ if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9'){ x = x * 10 + c - '0'; c = getchar(); }
    x *= f;
}
const int N = (int)2e5 + 10;
int s[N];
int len[N], n, tot;
struct SAM{
    int ch[N][26], pre[N], mxl[N], vis[N], last, cnt, ans[N];
    SAM(){ last = cnt = 1; }
    inline void Insert(register int c){
        register int p = last, np = ++cnt; last = np;
        mxl[np] = mxl[p] + 1;
        for (; p && !ch[p][c]; p = pre[p]) ch[p][c] = np;
        if (!p){ pre[np] = 1; return; }
        register int q = ch[p][c], nq = ++cnt;
        if (mxl[q] == mxl[p] + 1) { pre[np] = q; --cnt; return; }
        memcpy(ch[nq], ch[q], sizeof(ch[q]));
        mxl[nq] = mxl[p] + 1; pre[nq] = pre[q]; pre[q] = pre[np] = nq;
        for (; ch[p][c] == q; p = pre[p]) ch[p][c] = nq;
    }
    inline void Update(register int x, register int y){
        for (; x && vis[x] != y && vis[x] != -1; x = pre[x]){
            if (vis[x] != 0) vis[x] = -1;
            else vis[x] = y;
        }
    }
    inline void Solve(){
        tot = 0;
        //遍历所有串
        for (register int i = 1; i <= n; i++)
        for (register int j = 1, x = 1; j <= len[i]; j++)
            Update(x = ch[x][s[++tot]], i);
        for (register int i = 1; i <= cnt; i++) if (vis[i] != -1){
            register int x = vis[i];
            ans[x] += mxl[i] - mxl[pre[i]];
        }
        for (register int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    }
}sam;
int main(){
    read(n);
    for (register int i = 1; i <= n; i++){
        register char c; sam.last = 1;//新串last重置为1
        while ((c = getchar()) != '\n' && c != EOF){
            c -= 'a'; ++len[i]; s[++tot] = c;
            sam.Insert(c);
        }
    }
    sam.Solve();
    return 0;
}

附上自己画的SAM图，均由graphviz生成，有自动生成图形代码，博客中有(https://www.luogu.org/blog/yy1695651/yong-graphviz-hua-sam)

Sevenk Love Oimaster(https://www.luogu.org/problemnew/show/SP8093)

有兴趣再看看这道题，差不多做法