后缀自动机SAM

板子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
struct SAM {
    static constexpr int asz = 26;
    struct Node {
        int len;
        int fail;
        int cnt = 0;
        array<int, asz> next;
        Node() : len{}, fail{}, next{} {}
    };
    vector<Node> t;
    int tot = 0;
    SAM() {
        init();
    }
    void init() {
        t.assign(2, Node());
        t[0].next.fill(1);
        t[0].len = -1;
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    int extend(int p, int c) {
        if (t[p].next[c]) {
            int q = t[p].next[c];
            if (t[q].len == t[p].len + 1) {
                return q;
            }
            int nq = newNode();
            t[nq].len = t[p].len + 1;
            t[nq].fail = t[q].fail;
            t[nq].next = t[q].next;
            t[q].fail = nq;
            while (t[p].next[c] == q) {
                t[p].next[c] = nq;
                p = t[p].fail;
            }
            return nq;
        }
        int np = newNode();
        t[np].len = t[p].len + 1;
        while (!t[p].next[c]) {
            t[p].next[c] = np;
            p = t[p].fail;
        }
        t[np].fail = extend(p, c);
        t[np].cnt += 1;
        return np;
    }
    int extend(int p, char c, char offset = 'a') {
        return extend(p, c - offset);
    }

    int next(int p, int x) {
        return t[p].next[x];
    }

    int next(int p, char c, char offset = 'a') {
        return next(p, c - 'a');
    }

    int fail(int p) {
        return t[p].fail;
    }

    int len(int p) {
        return t[p].len;
    }
    int size() {
        return t.size();
    }
    int &cnt(int p) {
        return t[p].cnt;
    }
    void work(string s) {
        int p = 1;
        //vector<int> pos(1, 0);
        for (auto x : s) {
            p = extend(p, x);
            //pos.push_back(p);
        }
        tot = t.size() - 1;
        //return pos;
    }
    void getcnt(int len) {
        vector<int> tong(len + 1);
        vector<int> id(tot + 1);
        for (int i = 1; i <= tot; i++) tong[t[i].len]++;
        // 按照len[x]从小到大基数排序，相当于对SAM图进行拓扑排序
        for (int i = 1; i <= len; i++) tong[i] += tong[i - 1];
        for (int i = 1; i <= tot; i++) id[tong[t[i].len]--] = i;  // 排名为j的节点是状态i
        for (int i = tot; i >= 1; i--) {
            auto cur = t[id[i]];
            t[cur.fail].cnt += cur.cnt;
        }
        // 从后往前for,自底向上更新parent的right大小
    }
};

给定一个只包含小写字母的字符串 SS。字符串的价值为出现次数乘上该子串长度，不考虑只出现一次的子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
    string s;
    cin >> s;
    SAM sam;
    sam.work(s);
    n = s.size();
    sam.getcnt(n);
    ll ans = 0;
    for (int i = 2; i <= sam.tot; i++) {
        if (sam.t[i].cnt <= 1)
            continue;
        ans = max((ll)sam.t[i].cnt * sam.len(i), ans);
    }
    cout << ans << endl;
}

https://www.luogu.com.cn/problem/P1368求解最小循环串：

  • S 复制一份拼接在后面得到T = S + S，对T 构造SAM，然后在上面走|S| 步，每步都走最小的转移边即可。

想想为什么不会提前遇到中止节点？只有后缀会有终止节点，而长度不超过n的后缀一定在原串上会有endpos，所以肯定能走下去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
    cin >> n;
    SAM sam;
    int p = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p = sam.extend(p, a[i]);
    }
    for (int i = 1; i <= n; i++) {
        p = sam.extend(p, a[i]);
    }
    p = 1;
   vector<int>res;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 30; j++) {
            if (sam.next(p, j)) {
               res.push_back(j);
                p = sam.next(p, j);
                break;
            }
        }
    }
    for(auto x:res)cout<<x<<" ";
}

例题2.给出一个字符串S，|S| ≤ 250, 000。
令G[x] 表示S 的所有长度为x 的子串中，出现次数的最大值。
求G[1], G[2], · · · , G[|S|]。

Sol:构建S 的SAM，对于每个SAM 状态s，他能表示的子串长度范围是
(L[f(s)], L[s]]，这些子串的出现次数等价于|Right(s)|。那么问题变成用
|Right(s)| 去区间更新(L[f(s)], L[s]] 的最大值。
无脑线段树？喜提TLE。(spoj是这样的)

  • 怎么优化呢
    因为如果长度为len的后缀出现了x次，那这个后缀的后缀也至少出现这么多次，所以G[i] 是单调不增的，我们只用|Right(s)| 去更新G[L[s]]，然后使用倒着推标记，从后向前令G[i] = max(G[i], G[i + 1]) 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
    string s;
    cin >> s;
    SAM sam;
    sam.work(s);
    n = s.size();
    sam.getcnt(n);
    //ll ans = 0;
    vector<int> ans(n + 1);
    for (int i = 2; i <= sam.tot; i++) {
        ans[sam.len(i)]=max(ans[sam.len(i)],sam.cnt(i));
    }
    for (int i = n - 1; i >= 1; i--) ans[i] = max(ans[i], ans[i + 1]);
    for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
}

如何求∣Right(s)∣|Right(s)|?

  • 大常数做法
    前面说过，不存在两个前缀位于同一个状态中，而每个前缀S[1, i] 的
    Right 集合必然包括了i，因此我们在构建SAM 的时候，顺便维护
    count[np] = |Right[np]] = 1。然后运行一遍dfs，求子树之和即可。

  • 小常数做法
    dfs 本质为树DP，树DP 本质是按照拓扑序来进行DP，Suffix-Chain 树
    的拓扑序等价于按照所有状态的L[s] 从大到小排序-> 基数排序。（板子更新成这个了

重要trick：要求我们快速定位S[l, r] 在SAM上所在的状态。

3.给出一个字符串S，|S| ≤ 200, 000，给出Q ≤ 200, 000 次询问，每次需
要回答S[l, r] 在S 中共出现了多少次

Sol:本题可以用SA 的做法，转化为区间的查询，略。

  • 如果使用SAM，我们提前求出每个状态的|Right[s]|，询问就是要求我
    们快速定位S[l, r] 所在的状态
  • 我们知道S[l, r] 一定是S 的前缀S[1, r] 的后缀，而S 的前缀共有n 个，
    我们很容易找到S 的每个前缀对应的SAM 状态节点，不妨设S[1, i] 对
    应于状态pos[i]。
    由于S[l, r] 是S[1, r] 的后缀，他对应的状态一定位于pos[i] 的后缀链接
    上，也即我们要从pos[i] 到根root 这条树链上最浅的满足,L[x] ≥ r − l + 1 的状态。
  • 使用倍增即可。

代码总结：pos数组提前开1，满足查询的1base。倍增数组注意cache，以及空间全部要多开1，因为习惯于左闭右闭。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void solve() {
    string s;
    cin >> s;
    n = s.size();
    SAM sam;
    auto pos = sam.work(s);
    int tot = sam.tot;
    //***********************************//建fail数倍增预处理
    vector<vector<int>> e(tot + 1);
    for (int i = 2; i <= sam.tot; i++) {
        int fa = sam.fail(i);
        deb(fa, i);
        deb(sam.len(fa), sam.len(i));
        e[sam.fail(i)].push_back(i);
    }
    const int jin = __lg(tot);
    vector st(jin + 1, vector<int>(tot + 1));
    auto dfs = [&](auto self, int u) -> void {
        for (auto v : e[u]) {
            self(self, v);
            st[0][v] = u;
            sam.cnt(u) += sam.cnt(v);
        }
    };
    dfs(dfs, 1);
    for (int j = 1; j <= jin; j++) {
        for (int i = 1; i <= tot; i++) {
            st[j][i] = st[j - 1][st[j - 1][i]];
        }
    }
    //***********************************//回答询问
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        int p = pos[r];  // 注意下标偏移
        for (int j = jin; j >= 0; j--) {
            int nx = st[j][p];
            if (sam.len(nx) >= r - l + 1) {
                p = nx;
            }
        }
        cout << sam.cnt(p) << endl;
    }
}

5.给出一个字符串S，|S| ≤ 200, 000，给出Q ≤ 200, 000 次询问，每次需
要回答S[l, r] 在S[L, R] 中共出现了多少次。

Sol:我们依然将出现次数转化为满足条件的Right 的个数。
本题就是询问Right(s(S[l, r])) 中，在区间[L + r − l, R] 范围内的有多少
个值。
我们不能存储每个点的Right 集合，这是$O(n^2) $的。
前面讲过，求每个点的Right 具体都有哪些值，可以转化为子树询问，
进而变成dfs 序上的区间询问。

  • 做法1：问题就是dfs 序上对区间[dfsl[s], dfsr[s]] 询问，有多少个数字值
    在[L + r − l, R] 范围内，无脑持久化权值线段树，甚至还可以处理强制
    在线。

  • 做法2：如果不要求强制在线，可以先将每个询问挂在s(S[L, R]) 上，然
    后使用dsu on tree 进行离线处理。

  • upd：这里还可以给fail树建一个开点权值线段树，然后dfs的时候做线段树合并。具体来说，还是先找到模式串对应的树上结点，在这个子树的right节点里有多少值在[a,b][a,b]里面。只需要对权值线段树求区间和，但是每个线段都只有当前节点的信息，所以需要合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
struct SegmentTree {
#define mid ((l + r) >> 1)
    struct TREE {
        int l, r;
        int cnt;
    } tr[N * 20];  /// 2nlogn
    int tot;
    void push_up(int cur) {
        tr[cur].cnt = tr[tr[cur].l].cnt + tr[tr[cur].r].cnt;
    }
    void change(int &cur, int l, int r, int pos, int x) {
        if (!cur)
            cur = ++tot;
        if (l == r) {
            tr[cur].cnt = 1;
            return;
        }
        if (pos <= mid)
            change(tr[cur].l, l, mid, pos, x);
        else
            change(tr[cur].r, mid + 1, r, pos, x);
        push_up(cur);
    }
    int merge(int a, int b, int l, int r) {
        if (!a || !b)
            return a | b;
        if (l == r)
            return tr[a].cnt ? a : b;
        int cur = ++tot;
        tr[cur].l = merge(tr[a].l, tr[b].l, l, mid);
        tr[cur].r = merge(tr[a].r, tr[b].r, mid + 1, r);
        push_up(cur);
        return cur;
    }
    int query(int cur, int l, int r, int ql, int qr) {
        if (!cur || ql < l || qr > r || ql > qr)
            return 0;
        if (l == ql && r == qr)
            return tr[cur].cnt;
        if (qr <= mid)
            return query(tr[cur].l, l, mid, ql, qr);
        else if (ql > mid)
            return query(tr[cur].r, mid + 1, r, ql, qr);
        return query(tr[cur].l, l, mid, ql, mid) + query(tr[cur].r, mid + 1, r, mid + 1, qr);
    }
} seg;
//sam函数唯一变动
 auto work(string s) {
        int p = 1;
        vector<int> pos(1, 0);
        for (auto x : s) {
            p = extend(p, x);
            seg.change(rt[p], 1, n, t[p].len, 1);
            pos.push_back(p);
        }
        tot = t.size() - 1;
        return pos;
    }
    //没了
    void solve() {
    string s;
    cin >> s;
    n = s.size();
    SAM sam;
    auto pos = sam.work(s);
    int tot = sam.tot;
    //***********************************//建fail数倍增预处理
    vector<vector<int>> e(tot + 1);
    for (int i = 2; i <= sam.tot; i++) {
        int fa = sam.fail(i);
        deb(fa, i);
        deb(sam.len(fa), sam.len(i));
        e[sam.fail(i)].push_back(i);
    }
    const int jin = __lg(tot);
    vector st(jin + 1, vector<int>(tot + 1));
    auto dfs = [&](auto self, int u) -> void {
        for (auto v : e[u]) {
            self(self, v);
            st[0][v] = u;
            sam.cnt(u) += sam.cnt(v);
            rt[u] = seg.merge(rt[u], rt[v], 1, n);
        }
    };
    dfs(dfs, 1);
    for (int j = 1; j <= jin; j++) {
        for (int i = 1; i <= tot; i++) {
            st[j][i] = st[j - 1][st[j - 1][i]];
        }
    }
    //***********************************//回答询问
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int l, r, a, b;
        cin >> l >> r >> a >> b;
        int p = pos[r];  // 注意下标偏移
        for (int j = jin; j >= 0; j--) {
            int nx = st[j][p];
            if (sam.len(nx) >= r - l + 1) {
                p = nx;
            }
        }
        int ans = seg.query(rt[p], 1, n, a + r - l, b);
        cout << ans << endl;
    }
}

6.给出两个长度均小于100, 000 的字符串A 和B，求他们最长公共子串。
Sol:如果使用SAM，思路是构造一个串的SAM，将另一个串放在上面运行
（匹配）。

  • 我们要对于每个B 的前缀B[1, i]，找到一个他的最大后缀B[i − x + 1, i]，使得这个后缀是A 的SAM 可以表示的,这其实就是在sam上走边即可。然后读入下一个字符，如果能匹配就累加长度，不能匹配就跳fail树直到能匹配。若跳到根了，则当前的公共串长度为0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
    string s, t;cin >> s >> t;
    SAM sam; sam.work(s);
    int ans = 0;int res = 0;
    int p = 1;
    for (auto x : t) {
        int tmp = sam.next(p, x);
        if (tmp) {
            res++;p = tmp;
        } else {
            int q = sam.fail(p);
            while (q != 1 && sam.next(q, x) == 0) q = sam.fail(q);
            // 可能根本没有这个匹配根本没有模式串的字母
            p = sam.next(q, x);
            if (p)res = sam.len(q) + 1;
            else res = 0,p = 1;
            //及时还原正确的起点
        }
         ans = max(ans, res);
    }
       cout << ans << endl;
}

9.顺着第六题这个思路考虑求：给出两个串S 和T，求公共本质不同子串个数

Sol：造S 的SAM，将T 放在上面运行，对于每个状态state 求出能表示的
最大T 的子串长度len[state]，考虑怎么求？

  • 首先每个节点的最长公共子串已经在第六问的求解过程。设当前状态匹配的公共串长度为len，考虑后缀链接树的性质，则从该节点到根的每个点上也至少能匹配min(len,L[state])，所以我们需要拓扑序取max。这依然可以使用对长度基数排序，倒序拓扑更新。

  • 答案是∑statelen[state]−L[fa(state)]。\sum_{state}^{} len[state] − L[fa(state)]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
///sam内部更新：
 int &lc(int p) {
        return t[p].lc;
    }
    void getlc(int len) {
        vector<int> tong(len + 1);
        vector<int> id(tot + 1);
        for (int i = 1; i <= tot; i++) tong[t[i].len]++;
        // 按照len[x]从小到大基数排序，相当于对SAM图进行拓扑排序
        for (int i = 1; i <= n; i++) tong[i] += tong[i - 1];
        for (int i = 1; i <= tot; i++) id[tong[t[i].len]--] = i;  // 排名为j的节点是状态i
        for (int i = tot; i >= 1; i--) {
            auto cur = t[id[i]];
            deb(cur.fail, id[i]);
            t[cur.fail].lc = max(t[cur.fail].lc, cur.lc);
        }
        // 从后往前for,自底向上更新parent的right大小
    }
    
SAM sam;
void solve() {
    string s, t;
    cin >> s >> t;
    sam.work(s);
    n = s.size();
    ll ans = 0;
    int tot = sam.tot;
    int tmp = 0;
    int p = 1;
    for (auto x : t) {
        if (sam.next(p, x)) {
            tmp++;
            p = sam.next(p, x);
        } else {
            while (p > 1 && sam.next(p, x) == 0) p = sam.fail(p);
            if (sam.next(p, x)) {
                tmp = sam.len(p) + 1;
                p = sam.next(p, x);
            } else
                tmp = 0;
        }
        sam.lc(p) = max(sam.lc(p), tmp);
    }

    sam.getlc(n);
    for (int i = 2; i <= tot; i++) {
        ans += max(0, min(sam.lc(i), sam.len(i)) - sam.len(sam.fail(i)));
    }
    cout << ans << endl;
}

7.给出N ≤ 10 个长度均小于100, 000 的字符串，求他们的最长公共子串
长度。

Sol：使用SAM 的话，本题是一个多模式匹配，需要将6题的思路转变一下：
构造其中一个串A1 的SAM，然后将剩余的每个串$Ai 分别在上面运行。每次运行需要求对于SAM的每个节点，他能表示的最长的分别在上面运行。 每次运行需要求对于SAM 的每个节点，他能表示的最长的Ai$ 的子串长
度是多少。

  • 实现是将$Ai 用前面相同的放法在SAM上运行，然后拓扑更新取Max：如果用前面相同的放法在SAM 上运行，然后拓扑更新取Max： 如果Ai $的某个前缀匹配到了state 状态的len 长度，那么他一定也能匹
    配后缀链接上所有点的L[state∗]。
  • 运行九次后最终每个状态将会得到9 个匹配长度，将他们取Min 就可以得到这个
  • 状态与9 个串的最长公共子串长度。最终每个状态全局取MAX即可

关于时间复杂度的问题：你会发现每次拓扑更新都需要多次遍历所有sam的节点，考虑应该以最短的字符串建立sam，记为minlen。则考虑字符串总长度为SUM，则最多只有SUM/minlen个，则复杂度是正确的。不然会TLE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
  int &lc(int p) {
        return t[p].lc;
    }
    int &tmplc(int p) {
        return t[p].tmplc;
    }
    void getlc(int len) {
        vector<int> tong(len + 1);
        vector<int> id(tot + 1);
        for (int i = 1; i <= tot; i++) tong[t[i].len]++;
        // 按照len[x]从小到大基数排序，相当于对SAM图进行拓扑排序
        for (int i = 1; i <= n; i++) tong[i] += tong[i - 1];
        for (int i = 1; i <= tot; i++) id[tong[t[i].len]--] = i;  // 排名为j的节点是状态i
        for (int i = tot; i >= 1; i--) {
            auto cur = t[id[i]];
            deb(cur.fail, id[i]);
            t[cur.fail].lc = max(t[cur.fail].lc, cur.lc);
        }
        // 从后往前for,自底向上更新parent的right大小
    }
    SAM sam;
int ans = 0;
void duo(string t) {
    int tot = sam.tot;
    int tmp = 0;
    int p = 1;
    for (auto x : t) {
        if (sam.next(p, x)) {
            tmp++;
            p = sam.next(p, x);
        } else {
            while (p > 1 && sam.next(p, x) == 0) p = sam.fail(p);
            if (sam.next(p, x)) {
                tmp = sam.len(p) + 1;
                p = sam.next(p, x);
            } else
                tmp = 0;
        }
        sam.lc(p) = max(sam.lc(p), tmp);
    }
    sam.getlc(n);
    for (int i = 1; i <= tot; i++) {
        sam.tmplc(i) = min(sam.tmplc(i), sam.lc(i));
        sam.lc(i) = 0;
    }
}
void solve() {
    cin >> m;
    string s;
    vector<string> v(m);
    int mn = inf;
    int id = 0;
    for (int i = 0; i < m; i++) {
        cin >> v[i];
        if (mn > (int)v[i].size()) {
            mn = v[i].size();
            id = i;
        }
    }
    s = v[id];
    n = s.size();
    sam.work(s);
    // deb(s);
    int tot = sam.tot;
    for (int i = 0; i < m; i++) {
        if (id == i)
            continue;
        duo(v[i]);
    }
    for (int i = 2; i <= tot; i++) ans = max(ans, min(sam.len(i), sam.tmplc(i)));
    cout << ans << endl;
}

8.本质不同子串：造S 的SAM，$ \sum_{state} L[state] − L[f(state)]$ 即为答案

1
2
3
4
5
6
void solve() {
    string s;cin>>s;
    SAM sam;sam.work(s);ll ans=0;
    for(int i=2;i<=sam.tot;i++)ans+=sam.len(i)-sam.len(sam.fail(i));
    cout<<ans<<endl;
}

4.你有一台打字机，你需要用它打出一段只由小写字母构成的文本S。
设某个时刻，你已经打出来的文本为T，你可以执行两种操作：

  1. 花费A[ch] 块钱，将T 后面添加一个字符ch，得到T′ = T + ch，其
    中A[′a′ −′ z′] 给定。
  2. 花费B 块钱，将T 的一个子串S 复制一份，添加到T 的后面，得到
    T′ = T + S。
    问你为了得到S，最少的花费是多少。

Sol:不难看出，本题可以用DP 解决，设Cost[i] 表示得到S[1, i] 的最小代价。
考虑如何计算Cost[i]：

  1. 第一种操作带来的转移是：Cost[i] ← Cost[i − 1] + A[S[i]]。
  2. 第二种操作要求我们求最长的S[1, i] 的后缀S[i − x + 1, i]，使得他在
    S[1, i − x] 中也出现过，带来的转移是：
    Cost[i] ← min(Cost[i − x · · · , i − 1]) + B。
  • 但其实我们会发现这个cost数组一定是单调递增的，所以我们只需要关注最长的可行后缀，然后O(1)O(1)转移。怎么求这个长度x？
  • 对于每个前缀S[1, i]，如何求最长的后缀S[i − x + 1, i]，使得他在
    S[1, i − x] 中也出现过？
    用Right 的概念对问题进行转化：S[1, i−x] 中也出现过→ Right 集合包
    含[1, i − x] 中的至少一个位置→ Min(Right(S[i − x + 1, i])) ≤ i − x。
    因此我们需要使用拓扑更新，得到SAM 每个状态的Min(Right(s))。然
    后再配合ST 表，在S[1, i] 的后缀链接上倍增。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'),ch = getchar();
	x *= f;
}

const int N = 4e5 + 5;

class SAM
{
	public:
		int fail[N],tr[N][26],len[N],endpos[N],tot,last;
		void init()
		{
			for(int i = 0;i <= tot;i++) for(int j = 0;j < 26;j++) tr[i][j] = 0;
			for(int i = 0;i <= tot;i++) fail[i] = len[i] = endpos[i] = 0;
			tot = last = 1;
		}
		int ins(int x,int id)
		{
			int u = ++tot,p = last;
			len[u] = len[last] + 1; last = u; endpos[u] = id;
			while(p && tr[p][x] == 0) tr[p][x] = u,p = fail[p];
			if(!p) fail[u] = 1;
			else
			{
				int q = tr[p][x];
				if(len[q] == len[p] + 1) fail[u] = q;
				else
				{
					int cq = ++tot; endpos[tot] = 1e9;
					len[cq] = len[p] + 1; fail[cq] = fail[q];
					memcpy(tr[cq],tr[q],sizeof(tr[q]));
					fail[u] = fail[q] = cq;
					while(p && tr[p][x] == q) tr[p][x] = cq,p = fail[p];
				}
			}
			return u;
		}
}sam;

int n,s1,s2,f[N][19],pos[N];
char s[N];
LL dp[N];
vector <int> g[N];

void dfs(int u,int fa)
{
	f[u][0] = fa;
	for(auto x : g[u])
	{
		dfs(x,u);
		sam.endpos[u] = min(sam.endpos[u],sam.endpos[x]);
	}
}

int main()
{
	scanf("%s",s + 1);
	n = strlen(s + 1);
	read(s1); read(s2);
	sam.init();
	for(int i = 1;i <= n;i++) pos[i] = sam.ins(s[i] - 'a',i);
	for(int i = 2;i <= sam.tot;i++) g[sam.fail[i]].push_back(i);
	dfs(1,0);
	for(int j = 1;j <= 18;j++) for(int i = 1;i <= sam.tot;i++) f[i][j] = f[f[i][j - 1]][j - 1];
	for(int i = 1;i <= n;i++) dp[i] = 1e17;
	for(int i = 1;i <= n;i++)
	{
		int x = pos[i];
		for(int j = 18;j >= 0;j--) if(i - sam.len[f[x][j]] < sam.endpos[f[x][j]]) x = f[x][j];
		int y = sam.len[sam.fail[x]] + 1;
		if(x == 0) y = 0;
		if(i - y < sam.endpos[x]) x = f[x][0];
		int o = min(sam.len[x],i - sam.endpos[x]);
		dp[i] = min(dp[i - 1] + s1,dp[i - o] + s2);
	}
	printf("%lld\n",dp[n]);
	return (0-0); // QwQ
}

1.补充证明：dp数组一定单调递增。第一种操作下，显然增加。对于第二种操作，我们反证，假设dp[i]<dp[i-1],dp[i]的最优决策点是j，那么说明1–j内有j+1–i的子串，则说明1-j内有j+1–i-1的子串，则dp[i−1]≤dp[j]+s2=dp[i]dp[i-1] \le dp[j]+s2=dp[i].这与假设矛盾，证毕。

2.性质证明：每次的j是单调的

  • 考虑dp[i]的最优决策点是j，由dp数组单调可知，j的真实含义是最长的可行后缀。考虑i+1的决策点，j指针不可能回退。假设回退到k，说明k–i+1的串在前面出现过，但j–i+1都已经是i的最优解了，这显然，矛盾。

上面代码的核心：就是判断当前endpos表示当前节点表示的所有字符串中出现的最小端点，只有它大于转移点才能正确转移，我们需要找最小转移点。

  • 采用fail树上倍增，每次判断一下是不是不符合条件，不符合就继续跳。结束以后判断边界，如果这个状态的最小长度后缀都无法满足条件，就再向上跳一步。
  • 特判跳到fail树假的根节点0说明无法转移。向上跳一步一定满足条件，考虑倍增的性质。还有就是endpos介于 sam.len[sam.fail[x]] + 1和 sam.len(x)之间的情况，我们只需要取长度为min(i-endpos,sam.len(i));

11.给出一个模板串T，和n 个串Si，保证输入的Si 都是T 的子串。

Alice 和Bob 进行一场游戏，两人轮流操作，每次操作必须：

  1. 选择某一个串Si。
  2. 将Si 后面添加一个字符ch，要求S′i = Si + ch 必须也是T 的子串。
    不能操作者输，Alice 先行，问谁会赢得这个游戏。

Sol:不难看出，这是一个组合Nim 游戏，每个串单独来看，就是一个字符串
版本的取石子游戏。
因此要求我们去求每个独立游戏的SG 函数，每次操作是在字符串后面
新增一个字母，很容易联想到SAM。

  • 因此本题对T 构造SAM，然后再trans 转移图（DAG）上进行DP
    （dfs）求解每个状态的SG 函数值。
    判断所有独立游戏的SG 值异或和是否为0 即可判定游戏胜负。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void solve() {
    string s;
    while (cin >> s) {
        SAM sam;
        sam.work(s);
        cin >> m;
        int ans = 0;
        int tot = sam.tot;
        vector<int> sg(tot + 1);
        vector<bool> vis(tot + 1);
        auto dfs = [&](auto self, int u) {
            if (vis[u])
                return;
            vis[u] = true;
            set<ll> st;
            for (int i = 0; i < 26; i++) {
                if (sam.next(u, i)) {
                    int tmp = sam.next(u, i);
                    self(self, tmp);
                    st.insert(sg[tmp]);
                }
            }
            while (st.count(sg[u])) sg[u]++;
        };
        dfs(dfs, 1);
        auto cal = [&](string &t) {
            int p = 1;
            for (auto x : t) {
                p = sam.next(p, x);
            }
            return sg[p];
        };
        for (int i = 1; i <= m; i++) {
            string tt;
            cin >> tt;
            ans ^= cal(tt);
        }
        if (ans == 0)
            cout << "Bob" << endl;
        else
            cout << "Alice" << endl;
    }
}

SAM(后缀自动机)专题总结 - mikufun♘ - 博客园

给定多个模式串，每次查询给定一个字符串，问这个字符串在所有模式串中出现了多少次？（注意区分对比ac自动机解决的是模式串在查询的串中出现了多少次），这里问的是查询串出现了多少次？

  • 考虑不可能提前预处理查询串的border结构，ac自动机是离线结构，所以需要sam

串之间用(‘z’+1)连接，array需要多开空间。查询的时候只需要在后缀自动机上运行，如果没有出边，说明查询的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
char tmp = 'z' + 1;
void solve() {
    int n;
    cin >> n;
    vector<string> q(n + 1);
    for (int i = 1; i <= n; i++) cin >> q[i];
    SAM sam;
    string s;
    for (int i = 1; i <= n; i++) s += q[i] + tmp;
    sam.work(s);
    int len = s.size();
    sam.getcnt(len);
    auto query = [&](string t) {
        int p = 1;
        for (auto x : t) {
            if (sam.next(p, x) == 0)
                return 0;
            else
                p = sam.next(p, x);
        }
        return sam.cnt(p);
    };
    for (int i = 1; i <= n; i++) {
        cout << query(q[i]) << endl;
    }
}