收集一些SAM相关题目，关于SAM见这篇博客。

        以下题目不涉及题面，可点开标题自查。

[模板]后缀自动机

        洛谷上后缀自动机的模板题。
        一个串出现的次数，就是这个串对应状态的endpos集合的大小，这个大小可以递推得到，我们把它记为$f[i]$，这个东西在其它博客中也被记为$right[i]$。
        处理完这个大小后，遍历所有$f[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
#include <bits/stdc++.h>

using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[2000005];
struct Edge {
    int next, to;
} edge[2000005];
char op[2000005];
int l, ct = 1, last = 1, f[2000005], head[2000005];

inline void add(int x, int y) {//建parent树
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int c) {//建SAM
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1, f[np] = 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

void DFS(int x) {//DFS求f数组
    if (x == 0)return;
    for (int i = head[x]; i; i = edge[i].next)DFS(edge[i].to), f[x] += f[edge[i].to];//集合划分即为它们的和
}

long long ans = 0;

int main() {
    scanf("%s", op), l = strlen(op), ct = last = 1;
    for (int i = 0; i < l; i++)add(op[i] - 'a');
    for (int i = 2; i <= ct; i++)add(nd[i].fa, i);
    DFS(1);
    for (int i = 2; i <= ct; i++) {
        if (f[i] != 1)ans = max(ans, 1ll * f[i] * nd[i].len);
    }
    cout << ans;
    return 0;
}

[TJOI2015]弦论

        字符串字典序第k小子串模板题，需要根据重复子串计不计入重数来考虑。
        如果不计入重数，那么我们需要考虑每一个状态结点可以扩展得到的所有子串数目，由于SAM上的子串都是互不相同的，故可以用一遍DFS（严格来说是DP思想）求出。这样再在SAM上跑出第k小就很容易了。
        如果需要计入重数，再计算结点本身的数量时，就不是加一，而是加$f[x]$（见上文）。这里的$f[x]$就相当于计入重数。

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
#include <bits/stdc++.h>

#define N 500005<<1
using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[N];
struct Edge {
    int next, to;
} edge[N];
char op[N], ans[N];
int l, ct = 1, last = 1, f[N], head[N], n, k, dp[N];

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1, f[np] = 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}


int DP(int x) {
    if (x == 0)return 0;
    if (dp[x])return dp[x];
    for (int i = 0; i < 26; i++)dp[x] += DP(nd[x].ch[i]);
    return dp[x] += (n == 0 ? 1 : f[x]);
}

void DFS(int x) {
    if (x == 0)return;
    for (int i = head[x]; i; i = edge[i].next)DFS(edge[i].to), f[x] += f[edge[i].to];
}

void find(int now, int s) {
    if ((n == 0 ? (k == 1) : (k <= f[now]))) {
        ans[s] = '\0', printf("%s", ans);
        exit(0);
    } else k -= (n == 0 ? 1 : f[now]);
    for (int i = 0; i < 26; i++) {
        if (DP(nd[now].ch[i]) >= k)ans[s] = static_cast<char>('a' + i), find(nd[now].ch[i], s + 1);
        else k -= DP(nd[now].ch[i]);
    }
}

int main() {
    scanf("%s", op), l = strlen(op), ct = last = 1;
    for (int i = 0; i < l; i++)add(op[i] - 'a');
    for (int i = 2; i <= ct; i++)add(nd[i].fa, i);
    DFS(1), scanf("%d%d", &n, &k), k += (n == 0 ? 1 : f[1]), find(1, 0), printf("-1");
    return 0;
}

Long Long Message

        最长公共子串问题，之前曾介绍过后缀数组的做法。
        将一个串建成SAM，然后让另一个串在这上面跑，当某一条边可以走时，我们走这一条边，并令匹配数量加一。如果没有这一条边，考虑到目前的都是匹配的，因此找到当前已匹配部分的最长后缀，这当然就是parent tree上的父结点，然后找父结点是否有对应的边，转移即可。

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
#include <cstdio>
#include <cstring>
#include <iostream>

#define N 100005<<1
using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[N];
char op[N], B[N];
int l, ct = 1, last = 1, f[N], ans, tmp, now = 1;

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1, f[np] = 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

int main() {
    scanf("%s", op), l = strlen(op), ct = last = 1;
    for (int i = 0; i < l; i++)add(op[i] - 'a');
    scanf("%s", B);
    for (int i = 0; B[i]; i++) {
        if (nd[now].ch[B[i] - 'a'])now = nd[now].ch[B[i] - 'a'], ++tmp;
        else {
            while (now && nd[now].ch[B[i] - 'a'] == 0)now = nd[now].fa;
            if (!now)now = 1, tmp = 0;
            else tmp = nd[now].len + 1, now = nd[now].ch[B[i] - 'a'];
        }
        ans = max(ans, tmp);
    }
    cout << ans;
    return 0;
}

LCS2

        求多个串的最长公共子串。
        方法是对其中某一个串构造SAM，然后让其它的串在上面跑。在跑其中一个串时，对于SAM的每一个状态，我们都记录一个值，表示这个状态当前匹配的最大长度，跑完所有的串后，我们取每一个状态这个值的最小值，再在最小值中找出最大值就是答案。
        这里需要注意一个问题，当某一个串匹配时，它的所有后缀也是匹配的，必须对这些后缀状态的值也进行更新。根据SAM的性质，parent Tree上的子树就是这个后缀的所有延伸串，那么根据子树来更新这个结点的值即可。

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
#include <cstdio>
#include <cstring>
#include <iostream>

#define N 100005<<1
using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[N];
struct Edge {
    int to, next;
} edge[N];
char op[N];
int l, ct = 1, last = 1, head[N], p[N], ss[N];

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

void DFS(int x) {
    for (int i = head[x]; i; i = edge[i].next) DFS(edge[i].to), p[x] = max(p[x], min(p[edge[i].to], nd[x].len));//这里不能超过后缀的最大长度
    ss[x] = min(ss[x], p[x]);
}

int main() {
    scanf("%s", op), l = strlen(op), ct = last = 1;
    memset(ss, 127, sizeof(ss));
    for (int i = 0; i < l; i++)add(op[i] - 'a');
    for (int i = 2; i <= ct; i++)add(nd[i].fa, i);//建parent Tree
    while (scanf("%s", op) != EOF) {
        memset(p, 0, sizeof(p));
        int now = 1, tmp = 0;
        for (int i = 0; op[i]; i++) {
            if (nd[now].ch[op[i] - 'a'])now = nd[now].ch[op[i] - 'a'], ++tmp;
            else {
                while (now && nd[now].ch[op[i] - 'a'] == 0)now = nd[now].fa;
                if (now == 0)now = 1, tmp = 0;
                else tmp = nd[now].len + 1, now = nd[now].ch[op[i] - 'a'];
            }
            p[now] = max(p[now], tmp);
        }
        DFS(1);//一遍DFS更新答案
    }
    int ans = 0;
    for (int i = 2; i <= ct; i++)ans = max(ans, ss[i]);
    cout << ans;
    return 0;
}

[AHOI2013]差异

        其实就是统计后缀的lcp和。
        直接统计是$O(n^2)$的，考虑其它做法。首先注意到在SAM中parent Tree是按照后缀延伸得到的，不是lcp，在这里我们只需要翻转字符串，就可以用SAM解决了。
        翻转字符串后，建SAM，然后把所有前缀状态标记出来（根据SAM的性质，前缀状态必然互不相同），然后建出parent Tree，统计子树上被标记的结点数量和。
        很明显，两个前缀对应状态结点的LCA的len就是这两个前缀的lcs，放到原串上就是两个后缀的lcp，统计一下对于这个结点，有多少被标记的结点的LCA是它就可以了。直接枚举子树标记结点数量和，组合一下就能求出来。

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
#include <bits/stdc++.h>

#define N 500005<<1
using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[N];
struct Edge {
    int to, next;
} edge[N];
char op[N];
int l, ct = 1, last = 1, head[N], f[N], sum[N];

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

void DFS(int x) {
    for (int i = head[x]; i; i = edge[i].next)DFS(edge[i].to), sum[x] += sum[edge[i].to];
    if (f[x])++sum[x];
}

inline long long find(int x) {
    int ss = 0;
    long long p = 0;
    if (f[x])p = sum[x] - 1;
    for (int i = head[x]; i; i = edge[i].next)p += 1ll * ss * sum[edge[i].to], ss += sum[edge[i].to];
    return p * nd[x].len;
}

int main() {
    scanf("%s", op), l = strlen(op), reverse(op, op + l), ct = last = 1;
    for (int i = 0; i < l; i++)add(op[i] - 'a');
    for (int i = 2; i <= ct; i++)add(nd[i].fa, i);
    for (int i = 0, now = 1; i < l; i++)now = nd[now].ch[op[i] - 'a'], f[now]++;
    DFS(1);
    long long p = 0, zz = 0;
    for (int i = l, q = l - 1; i > 1; i--, q--)zz += 1ll * i * q;
    for (int i = l - 1, q = 1; i >= 1; i--, q++)zz += 1ll * i * q;
    for (int i = 2; i <= ct; i++)p += find(i);
    printf("%lld", zz - 2 * p);
    return 0;
}

SubString

        这题也太狠了，做法：LCT维护SAM的parent Tree。
        查询出现次数就是把询问串往SAM上跑，找到对应的状态结点，其$f[x]$值（就是所谓的$right[x]$）就是答案。
        但是本题中需要向已有的字符串后面再追加字符串，因此需要在线地构造SAM。这里的一个问题就是$f[x]$数组是不容易随SAM的更新而更新的，因此我们必须动态地维护parent Tree（其实是维护其子树点权和），既然有连边、删边操作，那么就用LCT来解决这个问题。
        子树和不好用LCT维护。注意到一个点的点权只会对它的所有祖先结点产生贡献，这样就转化为树上路径修改，单点查询问题，用LCT就可以了。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>

#define N 1500005
using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[N << 1];
int v[N], son[N][2], fa[N], lazy[N], sta[N], la[N], last = 1, ct = 1;
char op[N], opt[10];

inline bool isNotRoot(int x) {
    return son[fa[x]][0] == x || son[fa[x]][1] == x;
}

inline int identify(int x) {
    return son[fa[x]][1] == x;
}

inline void change(int f, int s, int w) {
    fa[s] = f, son[f][w] = s;
}

inline void rotate(int x) {
    int f = fa[x], g = fa[f], i = identify(x), j = identify(f);
    if (!isNotRoot(f))fa[x] = g;
    else change(g, x, j);
    change(f, son[x][i ^ 1], i), change(x, f, i ^ 1);
}

inline void pushr(int x) {
    swap(son[x][0], son[x][1]), lazy[x] ^= 1;
}

inline void pushdown(int x) {
    if (lazy[x])pushr(son[x][0]), pushr(son[x][1]), lazy[x] = 0;
    if (la[x]) {
        v[son[x][0]] += la[x], v[son[x][1]] += la[x];
        la[son[x][0]] += la[x], la[son[x][1]] += la[x], la[x] = 0;
    }
}

inline void splay(int x) {
    int i = 0, y = x;
    sta[++i] = y;
    while (isNotRoot(y))sta[++i] = y = fa[y];
    while (i)pushdown(sta[i--]);
    while (isNotRoot(x)) {
        int f = fa[x];
        if (isNotRoot(f)) {
            if (identify(x) == identify(f))rotate(f);
            else rotate(x);
        }
        rotate(x);
    }
}

inline void access(int x) {
    for (int i = 0; x; x = fa[i = x])splay(x), son[x][1] = i;
}

inline void makeRoot(int x) {
    access(x), splay(x), pushr(x);
}

inline void link(int x, int y) {
    makeRoot(x), fa[x] = y;
}

inline void cut(int x, int y) {
    makeRoot(x), access(y), splay(x);
    fa[y] = 0, son[x][1] = 0;
}

inline void split(int x, int y) {
    makeRoot(x), access(y), splay(y);
}
//以上是Link Cut Tree的部分
inline void add(int c) {//建SAM
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1, link(1, np);
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q, link(q, np);
        else {
            int nq = ++ct;//注意这里：需要先split保证q结点信息是最新的，否则会WA
            split(1, q), nd[nq] = nd[q], v[nq] = v[q], link(nd[nq].fa, nq), nd[nq].len = nd[p].len + 1;
            cut(nd[q].fa, q), nd[q].fa = nd[np].fa = nq, link(nq, q), link(nq, np);
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
    split(1, np), ++v[np], ++la[np];
}

inline void decode(char *s, int mask) {
    int l = strlen(s);
    for (int i = 0; i < l; i++)mask = (mask * 131 + i) % l, swap(s[i], s[mask]);
}

int main() {
    int q, mask = 0;
    scanf("%d%s", &q, op);
    for (int i = 0; op[i]; i++)add(op[i] - 'A');
    while (q--) {
        scanf("%s%s", opt, op), decode(op, mask);
        if (opt[0] == 'A')for (int i = 0; op[i]; i++)add(op[i] - 'A');
        else {
            int now = 1;
            for (int i = 0; op[i]; i++) {
                now = nd[now].ch[op[i] - 'A'];
                if (now == 0)break;
            }
            if (now == 0)printf("0\n");
            else split(1, now), printf("%d\n", v[now]), mask ^= v[now];
        }
    }
    return 0;
}

[APIO2014]回文串

        这个大概是回文自动机的模板题，但这里我们用SAM来解决。
        首先一个思路是遍历所有回文串，然后上SAM上找出现次数，这样遍历回文串上界达到$O(n^2)$，仅这一步就已经T了。
        注意到Manacher算法进行过程中，能够$O(n)$地遍历所有回文子串，这样我们遍历回文子串的复杂度就降到了$O(n)$，但是在SAM上找这个串的出现次数需要$O(n)$，总体是$O(n^2)$，仍然会T。
        接下来考虑树上倍增。对于一个回文串，其在原串中出现的位置是$[l, r]$，我们找到前缀$[1, r]$所对应的状态结点，沿parent Tree上向上跳，能够遍历其所有后缀，这里面一定有我们需要的子串。跳的过程显然可以用倍增算法降到$O(logn)$，这样总体时间复杂度为$O(nlogn)$。
        本题相当好，强烈建议不用PAM（回文自动机）而用SAM+Manacher来做一遍。

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
#include <bits/stdc++.h>

#define N 300005
using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[N << 1];
struct Edge {
    int next, to;
} edge[N << 1];
char op[N], op2[N << 1];
int l, l2, ct = 1, last = 1, f[N << 1], head[N << 1], gr[N << 1][20], p[N << 1];
int to[N << 1], id[N];

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1, f[np] = 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

void DFS(int x) {
    if (x == 0)return;
    for (int i = head[x]; i; i = edge[i].next) {
        gr[edge[i].to][0] = x;
        for (int j = 1; j < 20; j++)gr[edge[i].to][j] = gr[gr[edge[i].to][j - 1]][j - 1];
        DFS(edge[i].to), f[x] += f[edge[i].to];
    }
}

long long ans = 0;

inline void check(int l, int r) {
    if (l > r)return;
    l = to[l], r = to[r];//这里最好判一下#结尾/开始的影响
    int now = id[r];
    for (int i = 19; i >= 0; i--)if (nd[gr[now][i]].len >= r - l + 1)now = gr[now][i];
    ans = max(ans, 1ll * f[now] * (r - l + 1));
}

int main() {
    scanf("%s", op), l = strlen(op), ct = last = 1;
    for (int i = 0; i < l; i++)add(op[i] - 'a');
    for (int i = 0, now = 1; i < l; i++)now = nd[now].ch[op[i] - 'a'], id[i] = now;
    for (int i = 2; i <= ct; i++)add(nd[i].fa, i);
    DFS(1), l2 = 0;
    for (int i = 0, k = 0; i < l; k ^= 1) {
        if (!k)op2[l2++] = '#';
        else op2[l2++] = op[i++], to[l2 - 1] = i - 1;
    }
    op2[l2++] = '#';
    int pos = 0, r = 1;
    p[0] = 1;
    for (int i = 1; i < l2; i++) {
        if (i < r)p[i] = min(p[2 * pos - i], r - i);
        else p[i] = 1;
        for (; i - p[i] >= 0 && i + p[i] < l2 && op2[i - p[i]] == op2[i + p[i]]; ++p[i]) {
            check(i - p[i] + 2, i + p[i] - 2);
        }
        check(i - p[i] + 2, i + p[i] - 2);
        if (p[i] + i > r)r = p[i] + i, pos = i;
    }
    printf("%lld", ans);
    return 0;
}

[NOI2015]品酒大会

        对于0的情况（就是第一行的输出）很好办，直接统计一波即可。
        首先将翻转的字符串（参考上面题目的思想）建成SAM，然后建出parent Tree，在上面求出$f[x]$数组。枚举每一个状态结点，易知它们对答案的贡献就是：对这个结点对应的子串长度区间造成$\frac {f(x)(f(x)-1)} {2}$的贡献，将它们统计起来，可以用差分的方法$O(1)$修改。
        下面处理第二问。如果我们能够知道每一个状态结点的endpos，就可以很方便地统计最值，但这样在时间复杂度上显然是不可以的。注意到这些endpos对应的值，若要使它们中某两个数的乘积最大，要么是最大的两个数相乘，要么是最小的两个数相乘。用树型DP找出每一个状态结点的最大值、次大值、最小值和次小值，这个问题就解决了。然后将它们更新到对应的区间上，这里可以用线段树的标记永久化轻松实现。复杂度$O(n)$。

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
#include <bits/stdc++.h>

#define N 300005<<1
#define inf (1ll<<60)
using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[N];
struct Edge {
    int next, to;
} edge[N];
char op[N];
int len, ct = 1, last = 1, f[N], head[N], num[26], v[N];
long long ANS[N], V[(N) << 1], ANS2[N], max1[N], max2[N], min1[N], min2[N];

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int s) {
    int p = last, np = last = ++ct, c = op[s] - 'a';
    nd[np].len = nd[p].len + 1, f[np] = 1;
    max1[np] = min1[np] = v[s], max2[np] = -inf, min2[np] = inf;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            max1[nq] = max2[nq] = -inf, min1[nq] = min2[nq] = inf;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

void DFS(int x) {
    if (x == 0)return;
    for (int i = head[x]; i; i = edge[i].next) {
        DFS(edge[i].to);
        if (max1[edge[i].to] > max1[x])max2[x] = max(max1[x], max2[edge[i].to]), max1[x] = max1[edge[i].to];
        else max2[x] = max(max2[x], max1[edge[i].to]);
        if (min1[edge[i].to] < min1[x])min2[x] = min(min1[x], min2[edge[i].to]), min1[x] = min1[edge[i].to];
        else min2[x] = min(min2[x], min1[edge[i].to]);
        f[x] += f[edge[i].to];
    }
}

void build(int l = 1, int r = len, int k = 1) {
    V[k] = -inf;
    if (l == r)return;
    int mid = (l + r) >> 1;
    build(l, mid, k << 1), build(mid + 1, r, k << 1 | 1);
}

void update(int l, int r, long long s, int L = 1, int R = len, int k = 1) {
    if (L >= l && R <= r) {
        V[k] = max(V[k], s);
        return;
    }
    int mid = (L + R) >> 1;
    if (l > mid)update(l, r, s, mid + 1, R, k << 1 | 1);
    else if (r <= mid)update(l, r, s, L, mid, k << 1);
    else update(l, mid, s, L, mid, k << 1), update(mid + 1, r, s, mid + 1, R, k << 1 | 1);
}

void get(int l = 1, int r = len, int k = 1, long long s = -inf) {
    int mid = (l + r) >> 1;
    if (l == r)ANS2[l] = max(V[k], s);
    else get(l, mid, k << 1, max(V[k], s)), get(mid + 1, r, k << 1 | 1, max(V[k], s));
}

int main() {
    scanf("%d%s", &len, op), reverse(op, op + len), ct = last = 1;
    for (int i = 0; i < len; i++)scanf("%d", v + i);
    reverse(v, v + len);
    for (int i = 0; i < len; i++)add(i), ++num[op[i] - 'a'];
    for (int i = 2; i <= ct; i++)add(nd[i].fa, i);
    build(), DFS(1);
    for (int i = 2; i <= ct; i++) {
        int l = nd[nd[i].fa].len + 1, r = nd[i].len;
        if (f[i] > 1) {
            long long ans = max(1ll * max1[i] * max2[i], 1ll * min1[i] * min2[i]);
            update(l, r, ans);
            ANS[l] += 1ll * (f[i] - 1) * f[i] / 2, ANS[r + 1] -= 1ll * (f[i] - 1) * f[i] / 2;
        }
    }
    for (int i = 1; i <= len; i++)ANS[i] += ANS[i - 1];
    ANS[0] = 1ll * len * (len - 1) / 2, sort(v, v + len), get();
    ANS2[0] = max(1ll * v[0] * v[1], 1ll * v[len - 2] * v[len - 1]);
    for (int i = 0; i < len; i++)printf("%lld %lld\n", ANS[i], ANS2[i] == -inf ? 0 : ANS2[i]);
    return 0;
}

跳蚤

        好题（确实好题）。
        看到最小值最大想到二分答案，然后我们二分出一个答案k，找到第k小的子串，然后判定这个串合不合法即可。
        如何判断合不合法呢？注意到每一段子串中字典序最大的一个一定是某一个后缀，那么我们从后向前加入字符，每加入一个便引入了一个新的后缀，然后判定这个后缀与给定串的大小关系，如果大于给定串，则拆成两个子串，最后对比拆成子串的数量与k的大小关系。
        这里判定后缀与给定串的大小关系是一个不容易快速完成的操作，考虑字符串Hash。将原串哈希，并将二分出来的判定串哈希，用哈希的手段二分出两个串第一个不同的位置，就可以对比出两个串哪一个字典序更大。
        复杂度$O(nlog^2n)$。

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
#include <bits/stdc++.h>

#define N (200005<<1)
#define BASE 31
using namespace std;
struct Node {
    int ch[30], fa, len;
} nd[N];
char op[N];
int l, ct = 1, last = 1, k, len;
long long dp[N];
unsigned long long bin[N], hs[N], hs2[N];
char bb[N];

unsigned long long getHs(int l, int r) {//获得串[l,r](0开始)的hash值
    if (l == 0)return hs[r];
    return hs[r] - hs[l - 1] * bin[r - l + 1];
}

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

long long DP(int x) {
    if (x == 0)return 0;
    if (dp[x] != -1)return dp[x];
    dp[x] = 0;
    for (int i = 0; i < 30; i++)dp[x] += DP(nd[x].ch[i]);
    return ++dp[x];
}

void find(long long k, int s = 0, int now = 1) {
    if (k == 1) {
        bb[s] = '\0';
        return;
    } else --k;
    for (int i = 0; i < 30; i++) {
        if (DP(nd[now].ch[i]) >= k) {
            bb[s] = i + 'a', find(k, s + 1, nd[now].ch[i]);
            return;
        } else k -= DP(nd[now].ch[i]);
    }
}

inline bool cmp(int l, int r) {
    int a = 0, b = min(r - l + 1, len), mid;
    while (a < b) {//(,]
        if (b == a + 1) {
            if (getHs(l, l + b - 1) != hs2[b - 1])return op[l + b - 1] > bb[b - 1];
            return r - l + 1 > len;
        }
        mid = (a + b) >> 1;
        if (getHs(l, l + mid - 1) != hs2[mid - 1])b = mid;
        else a = mid;
    }
}

inline bool check(long long x) {
    find(x + 1), len = strlen(bb), hs2[0] = bb[0] - 'a' + 1;
    for (int i = 1; i < len; i++)hs2[i] = hs2[i - 1] * BASE + bb[i] - 'a' + 1;
    int num = 0, last = l - 1;
    for (int i = l - 1; i >= 0; i--)if (cmp(i, last))++num, last = i;
    return num + 1 <= k;
}

int main() {
    scanf("%d%s", &k, op), l = strlen(op), ct = last = 1, memset(dp, -1, sizeof(dp));
    for (int i = 0; i < l; i++)add(op[i] - 'a');
    bin[0] = 1, hs[0] = op[0] - 'a' + 1;
    for (int i = 1; i <= l; i++)bin[i] = bin[i - 1] * BASE;
    for (int i = 1; i < l; i++)hs[i] = hs[i - 1] * BASE + op[i] - 'a' + 1;
    long long l = 0, r = DP(1) - 1, mid;
    while (l < r) {//(,]
        if (r == l + 1) {
            find(r + 1);
            printf("%s", bb);
            return 0;
        }
        mid = (l + r) >> 1;
        if (check(mid))r = mid;
        else l = mid;
    }
    return 0;
}

[HAOI2016]找相同字符

        求匹配的子串方案数。
        将其中一个建成SAM，另一个按照求两个串最长公共子串的方法去匹配，记录每一个结点匹配的次数$tmp-len(fa)$。由于某一个串匹配也意味着它的后缀也匹配，因此需要将这个数量加到后缀中，也就是parent Tree中的父结点。

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
#include <bits/stdc++.h>

#define N 200005<<1
using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[N];
struct Edge {
    int next, to;
} edge[N];
char op[N];
int l, ct = 1, last = 1, f[N], head[N];
long long num[N], p[N];

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1, f[np] = 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

void DFS(int x) {
    if (x == 0)return;
    for (int i = head[x]; i; i = edge[i].next) {
        DFS(edge[i].to), f[x] += f[edge[i].to];
        num[x] += p[edge[i].to] * (nd[x].len - nd[nd[x].fa].len);
        p[x] += p[edge[i].to];
    }
}

int main() {
    long long ans = 0;
    scanf("%s", op), l = strlen(op), ct = last = 1;
    for (int i = 0; i < l; i++)add(op[i] - 'a');
    for (int i = 2; i <= ct; i++)add(nd[i].fa, i);
    scanf("%s", op);
    for (int i = 0, now = 1, tmp = 0; op[i]; i++) {
        if (nd[now].ch[op[i] - 'a'])now = nd[now].ch[op[i] - 'a'], ++tmp;
        else {
            while (now && nd[now].ch[op[i] - 'a'] == 0)now = nd[now].fa;
            if (now == 0)now = 1, tmp = 0;
            else tmp = nd[now].len + 1, now = nd[now].ch[op[i] - 'a'];
        }
        num[now] += tmp - nd[nd[now].fa].len, ++p[now];
    }
    DFS(1);
    for (int i = 2; i <= ct; i++)ans += f[i] * num[i];
    printf("%lld", ans);
    return 0;
}

识别子串

        建出SAM，找到$f[x]=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
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
#include <bits/stdc++.h>

#define N 100005<<1
#define inf 0x3f3f3f3f
using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[N];
struct Edge {
    int next, to;
} edge[N];
char op[N];
int len, ct = 1, last = 1, f[N], head[N], to[N], v[(N) << 1], v2[(N) << 1], ans[N];

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1, f[np] = 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

void build(int l = 1, int r = len, int k = 1) {
    if (l == r)ans[l] = v[k] = v2[k] = inf;
    else v[k] = v2[k] = inf, build(l, (l + r) >> 1, k << 1), build(((l + r) >> 1) + 1, r, k << 1 | 1);
}

void update(int l, int r, int s, int L = 1, int R = len, int k = 1) {
    if (L >= l && R <= r) {
        v[k] = min(v[k], s);
        return;
    }
    int mid = (L + R) >> 1;
    if (l > mid)update(l, r, s, mid + 1, R, k << 1 | 1);
    else if (r <= mid)update(l, r, s, L, mid, k << 1);
    else update(l, mid, s, L, mid, k << 1), update(mid + 1, r, s, mid + 1, R, k << 1 | 1);
}

void update2(int l, int r, int s, int L = 1, int R = len, int k = 1) {
    if (L >= l && R <= r) {
        v2[k] = min(v2[k], s);
        return;
    }
    int mid = (L + R) >> 1;
    if (l > mid)update2(l, r, s, mid + 1, R, k << 1 | 1);
    else if (r <= mid)update2(l, r, s, L, mid, k << 1);
    else update2(l, mid, s, L, mid, k << 1), update2(mid + 1, r, s, mid + 1, R, k << 1 | 1);
}

void DFS(int x) {
    if (x == 0)return;
    for (int i = head[x]; i; i = edge[i].next)DFS(edge[i].to), f[x] += f[edge[i].to];
}

void DFS2(int k = 1, int m = inf, int l = 1, int r = len) {
    if (l == r)ans[l] = min(min(m, v[k]) - l + 1, ans[l]);
    else DFS2(k << 1, min(m, v[k]), l, (l + r) >> 1), DFS2(k << 1 | 1, min(m, v[k]), ((l + r) >> 1) + 1, r);
}

void DFS3(int k = 1, int m = inf, int l = 1, int r = len) {
    if (l == r)ans[l] = min(min(m, v2[k]), ans[l]);
    else DFS3(k << 1, min(m, v2[k]), l, (l + r) >> 1), DFS3(k << 1 | 1, min(m, v2[k]), ((l + r) >> 1) + 1, r);
}

int main() {
    scanf("%s", op), len = strlen(op), ct = last = 1;
    for (int i = 0; i < len; i++)add(op[i] - 'a');
    for (int i = 2; i <= ct; i++)add(nd[i].fa, i);
    DFS(1), build();
    for (int i = 0, now = 1; i < len; i++)now = nd[now].ch[op[i] - 'a'], to[i] = now;
    for (int i = 0; i < len; i++) {
        int now = to[i];
        while (now && f[now] == 1) {
            update(i - nd[now].len + 2, i - nd[nd[now].fa].len + 1, i + 1);
            update2(i - nd[nd[now].fa].len + 1, i + 1, nd[nd[now].fa].len + 1);
            now = nd[now].fa;
        }
    }
    DFS2(), DFS3();
    for (int i = 1; i <= len; i++)printf("%d\n", ans[i]);
    return 0;
}

[Spoj]8093 Sevenk Love Oimaster

        广义后缀自动机。这里我们将所有串拼接起来，中间用一个特殊字符连接，然后把它们全丢进SAM，然后标记每一个前缀结点所属的串的编号。
        查询的时候，找到查询串对应的结点（没有则答案为0）。现在考虑这样一个问题，这个结点的endpos集合大小是很容易求的，如果我们也能够容易地知道这个集合的详细数据，那么匹配多少个串就可以求了。这个集合确实可以求，但是显然没有必要处理出所有结点的endpos集合。注意到在parent Tree中，这个状态结点的子树上的结点都以该结点为后缀，类比一下$f[x]$数组的求法，容易知道只有这棵子树上的前缀结点会影响答案。问题即转化为求子树上颜色的数量，直接离线跑莫队就完了。
        为什么要分隔字符串：分隔字符可以保证状态结点对应的串不会跨两个字符串。

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
107
108
#include <bits/stdc++.h>

#define N 100005<<2
using namespace std;
struct Node {
    int ch[30], fa, len;
} nd[N];
struct Edge {
    int next, to;
} edge[N];
char op[400005];
int len, ct = 1, last = 1, head[N], id[N], dfn[N], ID = 1, sz[N], to[N];
int be[N], base, num[10005];

struct Q {
    int l, r, ans, rk;

    bool operator<(const Q s) const {
        if (be[l] != be[s.l])return be[l] < be[s.l];
        return be[r] < be[s.r];
    }
} q[60005];

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

void DFS(int x) {
    to[ID] = x, dfn[x] = ID++, sz[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)DFS(edge[i].to), sz[x] += sz[edge[i].to];
}

bool cmp(const Q a, const Q b) {
    return a.rk < b.rk;
}

int n, m;

int main() {
    scanf("%d%d", &n, &m), ct = last = 1;
    for (int i = 1; i <= n; i++) {
        scanf("%s", op), len = strlen(op);
        for (int j = 0; j < len; j++)id[ct + 1] = i, add(op[j] - 'a');
        add(26);
    }
    for (int i = 2; i <= ct; i++)add(nd[i].fa, i);
    DFS(1);
    for (int t = 1; t <= m; t++) {
        scanf("%s", op);
        int now = 1, fg = 0;
        for (int i = 0; op[i]; i++) {
            if (nd[now].ch[op[i] - 'a'] == 0) {
                fg = 1;
                break;
            } else now = nd[now].ch[op[i] - 'a'];
        }
        if (fg)q[t].l = -1, q[t].r = -1, q[t].rk = t;
        else q[t].l = dfn[now], q[t].r = dfn[now] + sz[now] - 1, q[t].rk = t;
    }
    base = sqrt(ID);
    for (int i = 1; i < ID; i++)be[i] = (i - 1) / base + 1;
    sort(q + 1, q + m + 1);
    int l = 1, r = 1, ans = 0;
    for (int i = 1; i <= m; i++) {
        if (q[i].l == -1)continue;
        while (l > q[i].l) {
            ++num[id[to[l - 1]]];
            if (id[to[l - 1]] && num[id[to[l - 1]]] == 1)++ans;
            l--;
        }
        while (r < q[i].r) {
            ++num[id[to[r + 1]]];
            if (id[to[r + 1]] && num[id[to[r + 1]]] == 1)++ans;
            r++;
        }
        while (l < q[i].l) {
            --num[id[to[l]]];
            if (id[to[l]] && num[id[to[l]]] == 0)--ans;
            l++;
        }
        while (r > q[i].r) {
            --num[id[to[r]]];
            if (id[to[r]] && num[id[to[r]]] == 0)--ans;
            r--;
        }
        q[i].ans = ans;
    }
    sort(q + 1, q + m + 1, cmp);
    for (int i = 1; i <= m; i++)printf("%d\n", q[i].ans);
    return 0;
}

[bzoj3277]串

        仍然广义SAM，每一次放入串时，将last重置为根。（其实建广义SAM的方法就这一种和上一题那一种？）
        这样建SAM有什么好处？我们可以对比不将last重置为根（即将所有串连起来成为一个串）和这种方法的区别，这里给出结论：这样建SAM与前者的唯一区别是排除了所有跨串子串的干扰。这一句话如何理解？如果一个串是ab，另一个是c，那么前者建SAM会认为bc是一个合法的子串，而后者不会，这是它们的唯一区别。在其它方面（包括parent Tree等等）的性质完全一致。
        这样问题变得清晰了起来。要判断某一个串是多少串的子串，仍然沿用上一个题目的做法，标记前缀结点，然后数子树颜色个数。但是这里需要统计所有状态结点的答案，离线跑莫队或者树状数组显得太复杂，不如直接暴力统计：对于每一个前缀状态结点，暴力沿parent Tree树边向上跳，然后更新这个结点的答案。如果这个结点已经更新过了，因为我们统计的是种类数，直接跳过，所以需要标记哪些结点已经更新过答案了。可以证明，这样做的时间复杂度上界是$O(n\sqrt n)$。
        之后我们就可以统计答案了。对于一个合法的状态结点（即出现在至少k个串中），它会对它的子树上结点造成$len(x)-len(fa)$的贡献。于是统计parent Tree上前缀和，对于每一个串，将它的前缀结点前缀和加起来就是答案（很妙的做法）。

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
#include <bits/stdc++.h>

#define N (100005<<1)+100005
using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[N];
struct Edge {
    int next, to;
} edge[N];
int l, ct = 1, last = 1, head[N], n, k, vis[N];
long long sum[N], sz[N];
string op[100005];
vector<int> to[100005];

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

void DFS(int x, long long s) {
    sum[x] = s + 1ll * (sz[x] >= k) * (nd[x].len - nd[nd[x].fa].len);
    for (int i = head[x]; i; i = edge[i].next)DFS(edge[i].to, sum[x]);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    last = ct = 1, cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> op[i], last = 1;
        for (int j = 0; j < op[i].length(); j++)to[i].push_back(ct + 1), add(op[i][j] - 'a');
    }
    for (int i = 2; i <= ct; i++)add(nd[i].fa, i);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < op[i].length(); j++) {
            int now = to[i][j];
            while (now && vis[now] != i)++sz[now], vis[now] = i, now = nd[now].fa;
        }
    }
    DFS(1, 0);
    for (int i = 1; i <= n; i++) {
        long long ans = 0;
        for (int j = 0; j < op[i].length(); j++)ans += sum[to[i][j]];
        cout << ans << " ";
    }
    return 0;
}

[CTSC2012]熟悉的文章

        好题啊，强烈建议一做。
        首先需要二分答案都能看出来，关键是怎么判定答案的正确性。
        预处理一步，把作文库里的01串放到一个广义SAM里，然后把查询串每一位向左最多匹配的长度找出来，存到$maxl[x]$中，这一步复杂度$O(n)$。
        判定的时候考虑$DP$。令$dp[x]$表示$1$到$x$这一段最多匹配的数目，如果$x$这一位不匹配进去，那么$dp[x]$显然可以由$dp[x-1]$转移过来，如果匹配，就需要将$x$这一位的字符放到一个长度不小于$mid$（二分出来的答案）的子段里，那么转移方程就可以列出了：

        发现这里$i$的左右端点都是不降的，拿单调队列优化，复杂度就是$O(nlogn)$。

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
#include <bits/stdc++.h>

#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#define N 1000005<<1
using namespace std;
struct Node {
    int ch[2], fa, len;
} nd[N];
char op[N];
int ct = 1, last = 1, n, m, maxl[N], dp[N], len;
deque<int> dq;

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

inline void insert(int x) {
    while (!dq.empty() && dp[dq.back()] - dq.back() < dp[x] - x)dq.pop_back();
    dq.push_back(x);
}

inline int getMax(int x) {
    while (dq.front() < x)dq.pop_front();
    return dq.front();
}

inline bool check(int x) {
    dq.clear(), dp[0] = 0, insert(0);
    for (int i = 1, s; i <= len; i++) {
        dp[i] = dp[i - 1];
        if (i - x >= 1)insert(i - x);
        if (maxl[i] >= x && i - x >= 0)s = getMax(i - maxl[i]), dp[i] = max(dp[i], i + dp[s] - s);
    }
    return dp[len] >= 0.9 * len;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%s", op), last = 1;
        for (int j = 0; op[j]; j++)add(op[j] - '0');
    }
    for (int i = 1; i <= n; i++) {
        scanf("%s", op + 1), len = strlen(op + 1);
        for (int j = 1, now = 1, tmp = 0; j <= len; j++) {
            if (nd[now].ch[op[j] - '0'])++tmp, maxl[j] = tmp, now = nd[now].ch[op[j] - '0'];
            else {
                while (now && nd[now].ch[op[j] - '0'] == 0)now = nd[now].fa;
                if (now == 0)now = 1, tmp = 0, maxl[j] = 0;
                else tmp = nd[now].len + 1, now = nd[now].ch[op[j] - '0'], maxl[j] = tmp;
            }
        }
        int l = 0, r = len + 1, mid;
        while (l < r) {//[,)
            if (r == l + 1) {
                printf("%d\n", l);
                break;
            }
            mid = (l + r) >> 1;
            if (check(mid))l = mid;
            else r = mid;
        }
    }
    return 0;
}

[ZJOI2015]诸神眷顾的幻想乡

        我就不吐槽这个满满东方风格的命名了。
        首先一条树链一定是以某个叶子结点为根，再到某个叶子结点的路径上的一段连续区间。由于叶子最多只有20个，可以枚举所有叶子，从这个叶子开始，将从根开始的所有字符串加入到广义SAM中。
        对于某一个叶子，我们当然可以DFS出所有串，然后一个个加入SAM，但这样是$O(n^2)$的。一个方法是在分枝时记录last值，在DFS下一个儿子结点时将last重置回来，能节省跳转结点的时间（Get到了新的建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
#include <bits/stdc++.h>

using namespace std;
struct Node {
    int ch[10], fa, len;
} nd[5000005];
struct Edge {
    int next, to;
} edge[200005];
int ct = 1, last = 1, head[200005], v[200005], n, c, w[100005];

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

void DFS(int x, int fa) {
    int l = ct + 1;
    add(v[x]);
    for (int i = head[x]; i; i = edge[i].next)if (edge[i].to != fa)last = l, DFS(edge[i].to, x);
}

long long ans;

int main() {
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; i++)scanf("%d", v + i);
    for (int i = 1, x, y; i < n; i++)scanf("%d%d", &x, &y), add(x, y), add(y, x), ++w[x], ++w[y];
    for (int i = 1; i <= n; i++)if (w[i] == 1)last = 1, DFS(i, 0);
    for (int i = 2; i <= ct; i++)ans += nd[i].len - nd[nd[i].fa].len;
    printf("%lld", ans);
    return 0;
}

Special Substrings

        当时觉着太难不想做，现在发现这真是好题。
        就是统计所有前缀包含的所有回文串的本质不同前缀串数量。前缀不好处理，倒着将字符串插入SAM，这样前缀转后缀，就能用SAM处理了。
        用一遍Manacher求出所有本质不同回文串范围，存到一个数组中，将它们按照右端点排序。易知对于一个回文串，数组中一定会保留它第一次出现的位置，从而保证了答案的正确性。
        对于一个前缀，在数组中截取它包含的回文串，然后在SAM上找到这个回文串的左端点对应的状态结点编号，用倍增的方法向上跳跃，找到回文串所在的状态结点编号。这时这个结点到根的路径上结点对应串都是这个回文串的合法子串，并且互不相同。
        下一步显然是将这些串计入答案，不过它们可能也是另一个回文串的前缀，会重复计入，因此我们记录每一个结点计入答案的数量，遇到已经计入的直接返回即可。可以证明，这样做每一个结点只会遍历很少的次数，对于整个过程复杂度为$O(n)$，总时间复杂度为$O(nlogn)$。

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
#include <bits/stdc++.h>

#define N (300005<<1)
using namespace std;
struct Node {
    int ch[26], fa, len;
} nd[N];
struct Edge {
    int next, to;
} edge[N];

struct P {
    int l, r;

    P(int a, int b) : l(a), r(b) {}

    bool operator<(P s) {
        return r < s.r;
    }
};

char op[N], op2[N];
int len, ct = 1, last = 1, head[N], len2, p[N], to[N], gr[N][22], num[N], now, id[300005];
vector<P> vvp;
long long ans;

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void add(int c) {
    int p = last, np = last = ++ct;
    nd[np].len = nd[p].len + 1;
    while (p && !nd[p].ch[c])nd[p].ch[c] = np, p = nd[p].fa;
    if (!p)nd[np].fa = 1;
    else {
        int q = nd[p].ch[c];
        if (nd[q].len == nd[p].len + 1)nd[np].fa = q;
        else {
            int nq = ++ct;
            nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
            while (p && nd[p].ch[c] == q)nd[p].ch[c] = nq, p = nd[p].fa;
        }
    }
}

inline void insert(int l, int r) {
    if (l > r)return;
    if (l % 2 && r % 2)vvp.push_back(P(to[l], to[r]));
}

void DFS(int x) {
    for (int i = head[x]; i; i = edge[i].next) {
        gr[edge[i].to][0] = x;
        for (int j = 1; j < 22; j++)gr[edge[i].to][j] = gr[gr[edge[i].to][j - 1]][j - 1];
        DFS(edge[i].to);
    }
}

inline void solve(int x) {
    int s = vvp[x].r - vvp[x].l + 1, p = id[vvp[x].l];
    for (int i = 21; i >= 0; i--)if (nd[gr[p][i]].len >= s)p = gr[p][i];
    while (p && (num[p] < (nd[p].len > s ? s - nd[nd[p].fa].len : nd[p].len - nd[nd[p].fa].len))) {
        ans += (nd[p].len > s ? s - nd[nd[p].fa].len : nd[p].len - nd[nd[p].fa].len) - num[p];
        num[p] += (nd[p].len > s ? s - nd[nd[p].fa].len : nd[p].len - nd[nd[p].fa].len) - num[p];
        p = nd[p].fa;
    }
}

int main() {
    scanf("%d%s", &len, op), ct = last = 1;
    for (int i = len - 1; i >= 0; i--)add(op[i] - 'a');
    for (int i = 2; i <= ct; i++)add(nd[i].fa, i);
    for (int i = len - 1, p = 1; i >= 0; i--)id[i] = p = nd[p].ch[op[i] - 'a'];
    for (int i = 0, k = 0; i < len; k ^= 1) {
        if (!k)op2[len2++] = '#';
        else op2[len2++] = op[i++], to[len2 - 1] = i - 1;
    }
    op2[len2++] = '#';
    int pos = 0, r = 1;
    p[0] = 1;
    for (int i = 1; i < len2; i++) {
        if (i < r)p[i] = min(p[2 * pos - i], r - i);
        else p[i] = 1;
        for (; i - p[i] >= 0 && i + p[i] < len2 && op2[i - p[i]] == op2[i + p[i]]; ++p[i]) {
            insert(i - p[i] + 1, i + p[i] - 1);
        }
        insert(i - p[i] + 1, i + p[i] - 1);
        if (p[i] + i > r)r = p[i] + i, pos = i;
    }
    sort(vvp.begin(), vvp.end()), DFS(1);
    for (int i = 0; i < len; i++) {
        while (now < vvp.size() && vvp[now].r <= i)solve(now), ++now;
        printf("%lld\n", ans);
    }
    return 0;
}