跳转至

后缀自动机（Suffix Automaton, SAM）

字符串 \(s\) 的 SAM 是一个接受 \(s\) 的所有后缀的最小 DFA。

SAM 是一个 DAG，且仅有一个根（\(1\) 号节点），从根节点出发的每一条路径都代表一个原串的不同子串。因此 SAM 是一种子串结构。同时求 SAM 的过程中还会得到副产物 \(\operatorname{link}\) 树，也非常有用。

到达某个状态的路径可能不止一条，因此我们说一个状态对应一些字符串的集合，这个集合的元素对应这些路径。

基本定义

\(\operatorname{endpos}\) 等价类

对于文本串 \(s\)，定义 \(t\) 的 \(\operatorname{endpos}\) 集合表示 \(t\) 在 \(s\) 中出现的所有位置（此处指结束位置）组成的集合。例如，对于字符串 \(s=\texttt{abcbc}\)，\(t=\texttt{bc}\)，我们有 \(\operatorname{endpos}_s(t)=\{2,4\}\)（从 \(0\) 开始编号）。

这样字符串 \(s\) 的所有非空子串都可以根据它们的 \(\operatorname{endpos}\) 集合被划分为若干等价类（同一等价类内的所有子串的 \(\operatorname{endpos}\) 集合相等）。记 \(s\) 的子串 \(t\) 所在的等价类为 \([t]_s\) 。

注意到 SAM 的每个状态和一个等价类 \(w\) 对应。如果不这样做，单个状态中的两个不同等价类添加一个相同的字符 \(c\) 之后可能转移到两个完全不同的状态，这不符合自动机的定义。

记等价类 \(u\) 中最长子串的长度为 \(len[u]\)。

性质

两个子串的 \(\operatorname{endpos}\) 集合要么不交，要么包含，因为 \(\operatorname{endpos}\) 具有包含关系的两个子串 \(t_1,t_2\) 一定具有后缀关系；

对于同一 \(\operatorname{endpos}\) 等价类的任一两个子串，较短者为较长者的后缀，且该等价类中的子串长度恰好覆盖一个区间 \([\operatorname{minlen},\operatorname{len}]\)。

经过一条转移边，等价类的 \(len\) 至少增加 \(1\)；

定义等价类 \(w\) 的 \(\operatorname{link}\) 指针指向另一个不同等价类，该等价类是 \(w\) 的后缀，且最长。

容易发现，所有等价类的 \(\operatorname{link}\) 构成一棵树，并且每个节点的所有祖先等价类内的所有子串都是当前等价类中任意一个子串的后缀。

性质

跳一条 \(\operatorname{link}\) 边，\(len\) 一定变小。

线性求 SAM

SAM 的建立过程是在线的，即从左往右逐个添加字符。

设当前已经添加了 \(s\) 的 \([1,i-1]\) 前缀 \(w\)，我们还需要额外用一个变量 \(last\) 存储 \(w\) 所在的等价类状态。考虑加入 \(c=s[i]\)。容易发现新产生的子串 \([1,i]\) 一定不存在于原来的 SAM 上。因此我们新建一个节点，记作 \(cur\)，然后直接连接一条 \(last\rightarrow cur\) 的边，这样就会新产生一条 \(1\rightarrow cur\) 的路径，表示加入 \([1,i]\) 子串。

考虑如何处理 \(cur\) 的 \(\operatorname{link}\) 指针：从 \(last\) 开始跳 \(\operatorname{link}\)，找到第一个（即最长的）具有 \(c\) 转移边的等价类 \(p\)。显然 \(p\) 中的所有子串都是 \(w\) 的后缀。

int cur = ++nn, p = last;
a[cur].len = a[p].len + 1;

while(p && !a[p].chd[c]) {
    a[p].chd[c] = cur;
    p = a[p].fa;
}

若跳到根节点都没有找到 \(p\)，则说明 \(c\) 字符在 \(w\) 中没有出现过，\(cur\) 的所有后缀都在同一个等价类中，\(\operatorname{link}(cur)=1\)。

记 \(q=p\rightarrow c\)，容易发现 \(q\) 是 \(cur\) 的后缀。这说明在加入新字符 \(s[i]=c\) 以前，SAM 就已经包含了 \(q\) 等价类，因此 \(\operatorname{endpos}(q)\) 会比 \(\operatorname{endpos}(s[1,i])=\{i\}\) 至少多包含一个元素，因此 \(longest(p)+c\) 和 \(cur\) 不在同一个等价类中。根据定义，\(\operatorname{link}(cur)=[longest(p)+c]_w\)。

SAM1

然而我们只考虑了 \(longest(p)+c\) 子串，并没有考虑 \(q\) 等价类的其它子串。如果 \(q\) 中存在更长的子串 \(r\)，那么显然 \(r\) 和 \(longest(p)+c\) 就不在同一等价类内了，因为 \(longest(p)+c\) 的 \(\operatorname{endpos}\) 会多一个元素 \(i\)（\(r\) 显然不是 \(cur\) 的后缀），发生了状态的分裂。

考虑如何处理状态的分裂。注意到新字符 \(s[i]=c\) 会使 \(q\) 等价类内 \(len>p.len+1\) 的子串和 \(len\le p.len+1\) 的子串分裂成了两个不同的等价类。

因此我们新开一个状态节点 \(nq\)，并将 \(q\) 中 \(len\le p.len+1\) 的子串移动到 \(nq\) 中：依次执行

int nq = ++nn;
len[nq] = len[p] + 1;
for(int i = 0; i < 26; i++) chd[nq][i] = chd[q][i];
link[nq] = link[q];
link[q] = nq;
link[cur] = nq;

接下来需要重定向某些状态，将它们的 \(\operatorname{link}\) 从 \(q\) 改变为 \(nq\)。我们枚举 \(p\) 的所有后缀，如果这些后缀还有向 \(q\) 的连边，则将它们都指向 \(nq\) 即可。

while(p && a[p].chd[c] == q) {
    a[p].chd[c] = nq;
    p = a[p].fa;
}
完整代码 
 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
struct Node {
    int chd[26];
    int fa, len;
    inline Node() {
        for(int i = 0; i < 26; i++) chd[i] = 0;
        fa = len = 0;
    }
} a[N];
int nn = 1;
int last = 1;

void insert(int c) {
    int cur = ++nn, p = last;
    a[cur].len = a[p].len + 1;
    while(p && !a[p].chd[c]) {
        a[p].chd[c] = cur;
        p = a[p].fa;
    }
    if(!p) {
        a[cur].fa = 1;
    } else {
        int q = a[p].chd[c];
        if(a[q].len == a[p].len + 1) {
            a[cur].fa = q;
        } else {
            int nq = ++nn;
            a[nq].len = a[p].len + 1;
            for(int i = 0; i < 26; i++) a[nq].chd[i] = a[q].chd[i]; // 复制状态
            a[nq].fa = a[q].fa;
            a[cur].fa = a[q].fa = nq;
            while(p && a[p].chd[c] == q) {
                a[p].chd[c] = nq;
                p = a[p].fa;
            }
        }
    }
    last = cur;
}

时间复杂度分析

除去 while 循环的其它位置显然都是单次 \(O(1)\)，均摊线性的。考虑证明两个 while 循环的均摊复杂度。

记 \(SC(x)\) 表示从 \(x\) 开始不断跳 \(link\) 直到跳到根，形成的一串 \(x\rightarrow \cdots \rightarrow 1\) 的序列（返根链）。

若一个字符串 \(t\) 是其等价类 \([t]_s\) 中最长的一个，则称 \(t\) 代表 该等价类。

若一条 \(c\)-转移边 从 \(x\) 指向 \(y\)，且 \(y.len=x.len+1\)，则称该转移边为主要的，否则为次要的。

Lemma 2.4

如果字符串 \(x\) 代表的等价类 \([x]_s\) 有一条 \(c\)-转移边 指向字符串 \(y\) 代表的等价类 \([y]_s\)（即 \([x]_s\rightarrow_c [y]_s\)），则 \(|SC(y)|=|SC(x)|-k+1\)，其中 \(k\) 表示 \(SC(x)\rightarrow SC(y)\) 中（跨过两条链）的次要边的数量。

Lemma 2.4 证明

注意到 \(SC(y)\) 中的每个状态（除去根节点）都有且仅有一条主要的入边。并且 \(SC(y)\) 中的每个状态（除去根节点）的入边的出发节点一定位于 \(SC(x)\)。同时 \(SC(x)\) 中的每个状态都有且仅有一条向 \(SC(y)\) 中状态的 \(c\)-转移边。

容易发现从 \(SC(x)\) 出发每连一条次要边，\(SC(y)\) 就会比 \(SC(x)\) 多一个点。同时考虑到 \(SC(y)\) 中的根节点没有入边，因此要 \(+1\)。证毕。

注意到两个 while 循环每次迭代（除去第一个 while 循环的起始边界）都会从 \(SC(w)\) 到 \(SC(wc)\) 连接一条次要边。记 \(k\) 为总循环次数，根据 Lemma 2.4，有

\[ \begin{align*} |SC(wc)|&\le |SC(w)|-(k-1)+1\\ &= |SC(w)|-k+2 \end{align*} \]

若调用一次 insert() 产生了 \(k\) 的时间复杂度，则会消耗 \(k\) 的势能。而总共产生的势能是 \(O(n)\) 的。证毕。

参考文献：The Smallest Automaton Recognizing the Subwords of a Text Page 16 Lemma 2.4 2.5

P3804 【模板】后缀自动机

题意

给定一个只包含小写字母的字符串 \(S\)。请你求出 \(S\) 的所有出现次数不为 \(1\) 的子串的出现次数乘上该子串长度。输出乘积的最大值。

\(|S|\le 10^6\)

考虑求出 SAM 上每个等价类的出现次数（即 \(\operatorname{endpos}\) 集合大小），然后直接用等价类的 \(len\times cnt\) 更新答案即可。

考虑使用 \(\operatorname{link}\) 树转移。由于 \(\operatorname{link}\) 树上两个没有祖孙关系的状态的 \(\operatorname{endpos}\) 无交，反之则一定包含。因此一个 naive 的想法是直接求出 \(\operatorname{link}\) 树上的子树大小减 \(1\) 作为出现次数。然而我们注意到，当一个等价类的 \(longest\) 子串是 \(S\) 的前缀时，该前缀不会被统计到（因为它无法作为任何子串的真后缀），否则一定能被统计到。

因此建立 SAM 时，应给每个前缀都增加 \(w_0=1\) 的权值。得到整个字符串的 SAM 之后，建出 \(\operatorname{link}\) 树，在 \(\operatorname{link}\) 树上做 dfs，将子节点的权值加入当前节点的权值即可。

代码 
 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
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int N = 2E6 + 10;

struct Edge {
    int v, next;
} pool[N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

struct Node {
    int chd[26];
    int fa, len;
    inline Node() {
        for(int i = 0; i < 26; i++) chd[i] = 0;
        fa = len = 0;
    }
} a[N];
int nn = 1;
int last = 1;

int f[N];

void insert(int c) {
    int cur = ++nn;
    a[cur].len = a[last].len + 1;
    f[cur] = 1;
    int p = last;
    while(p && !a[p].chd[c]) {
        a[p].chd[c] = cur;
        p = a[p].fa;
    }
    if(!p) {
        a[cur].fa = 1;
    } else {
        int q = a[p].chd[c];
        if(a[q].len == a[p].len + 1) {
            a[cur].fa = q;
        } else {
            int nq = ++nn;
            a[nq].len = a[p].len + 1;
            for(int i = 0; i < 26; i++) a[nq].chd[i] = a[q].chd[i];
            a[nq].fa = a[q].fa;
            a[cur].fa = a[q].fa = nq;
            while(p && a[p].chd[c] == q) {
                a[p].chd[c] = nq;
                p = a[p].fa;
            }
        }
    }
    last = cur;
}

ll ans;

void dfs(int u) {
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        dfs(v);
        f[u] += f[v];
    }
    if(f[u] > 1) ans = max(ans, (ll)f[u] * a[u].len);
}

string s;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> s;
    for(int i = 0; i < s.size(); i++) {
        insert(s[i] - 'a');
    }
    for(int i = 2; i <= nn; i++) {
        addEdge(a[i].fa, i);
    }

    dfs(1);

    cout << ans << endl;

    return 0;
}

P3975 [TJOI2015] 弦论

题意

对于一个给定的长度为 \(n\) 的字符串，求出它的第 \(k\) 小子串是什么。

题目会额外输入一个整数 \(t\)（\(t\in \{0,1\}\)），\(t\) 为 \(0\) 表示不同位置的相同子串算一个；\(t\) 为 \(1\) 表示不同位置的相同子串算多个。

\(n\le 5\times 10^5,\ k\le 10^9\)

因为 SAM 上从根出发的每一条路径代表一个子串，同时 \(\operatorname{link}\) 树可以求得每个子串出现的次数 \(f[u]\)（若 \(t=0\)，则 \(f[u]=1\)，否则 \(f[u]=\sum_{fa[v]=u} f[v]+w_0\)）。我们可以先求出 SAM 每个状态出发能到达多少个不同子串，记为 \(s[u]\)；然后直接从根节点出发试填即可。

注意，若子串以当前状态结尾，则其字典序比该节点的所有儿子都小。因此应在试填每个节点时先考虑这种情况。

int sum = (u != 1) * f[u];
if(k <= sum) return;
代码 
  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
120
121
122
123
124
125
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int N = 1E6 + 10;

struct Edge {
    int v, next;
} pool[N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

struct Node {
    int chd[26];
    int fa, len;
    inline Node() {
        for(int i = 0; i < 26; i++) chd[i] = 0;
        fa = len = 0;
    }
} a[N];
int nn = 1;
int last = 1;

string str;
int t, k;

ll f[N], s[N];

void insert(int c) {
    int cur = ++nn, p = last;
    f[cur] = 1;
    a[cur].len = a[last].len + 1;
    while(p && !a[p].chd[c]) {
        a[p].chd[c] = cur;
        p = a[p].fa;
    }
    if(!p) {
        a[cur].fa = 1;
    } else {
        int q = a[p].chd[c];
        if(a[q].len == a[p].len + 1) {
            a[cur].fa = q;
        } else {
            int nq = ++nn;
            a[nq].len = a[p].len + 1;
            for(int i = 0; i < 26; i++) a[nq].chd[i] = a[q].chd[i];
            a[nq].fa = a[q].fa;
            a[q].fa = a[cur].fa = nq;
            while(p && a[p].chd[c] == q) {
                a[p].chd[c] = nq;
                p = a[p].fa;
            }
        }
    }
    last = cur;
}

void get_cnt(int u) {
    // 这张图是 link 树
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        get_cnt(v);
        f[u] += f[v];
    }
    if(!t) f[u] = 1;
}

// 求出 SAM 子“树”和
bool vis[N];
void get_sum(int u) {
    if(vis[u]) return;
    vis[u] = 1;
    for(int i = 0; i < 26; i++) {
        int v = a[u].chd[i];
        if(!v) continue;
        get_sum(v);
        s[u] += s[v];
    }
    s[u] += f[u];
}

// 试填法
void get_res(int u) {
    int sum = (u != 1) * f[u];
    if(k <= sum) return;
    for(int i = 0; i < 26; i++) {
        int v = a[u].chd[i];
        if(!v) continue;
        if(k <= sum + s[v]) {
            k -= sum;
            putchar(i + 'a');
            get_res(v);
            return;
        }
        sum += s[v];
    }
    throw -1;
}

int main() {

    cin >> str >> t >> k;
    for(int i = 0; i < str.size(); i++) {
        insert(str[i] - 'a');
    }
    for(int i = 2; i <= nn; i++) {
        addEdge(a[i].fa, i);
    }

    try {
        get_cnt(1);
        get_sum(1);
        get_res(1);
    } catch(int x) {
        cout << -1;
    }

    cout << '\n';

    return 0;
}

SP1811 LCS

题意

输入两个字符串 \(s,t\)，输出它们的最长公共子串长度，若不存在公共子串则输出 \(0\)。

\(|s|,|t|\le 2.5\times 10^5\)。

由于 SAM 是一种子串结构，即 SAM 接受原串的所有子串。因此我们可以建出 \(s\) 的 SAM，然后用 \(t\) 在上面匹配。

考虑如何处理失配的情况。假设当前正在匹配字符 \(t[i]=c\)，但 \(cur\) 状态不具有 \(c\)-转移边。此时我们可以跳 \(\operatorname{link}\) 树，枚举 \(cur\) 的有效后缀，不断扩充 \(\operatorname{endpos}\) 集合，直到 \(\operatorname{endpos}\) 中存在一个位置 \(x\)，满足 \(s[x+1]=c\)，即状态 \(cur\) 存在 \(c\)-转移边，此时即可继续匹配。

若发现 \(s\) 中不包含 \(c\) 字符，则直接跳过 \(t[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
#include<iostream>
#include<cstring>
using namespace std;
const int N = 5E5 + 10;

struct Node {
    int chd[26];
    int fa, len;
    inline Node() {
        for(int i = 0; i < 26; i++) chd[i] = 0;
        fa = len = 0;
    }
} a[N];
int nn = 1;
int last = 1;

void insert(int c) {
    int cur = ++nn, p = last;
    a[cur].len = a[last].len + 1;
    while(p && !a[p].chd[c]) {
        a[p].chd[c] = cur;
        p = a[p].fa;
    }
    if(!p) {
        a[cur].fa = 1;
    } else {
        int q = a[p].chd[c];
        if(a[q].len == a[p].len + 1) {
            a[cur].fa = q;
        } else {
            int nq = ++nn;
            a[nq].len = a[p].len + 1;
            for(int i = 0; i < 26; i++) a[nq].chd[i] = a[q].chd[i];
            a[nq].fa = a[q].fa;
            a[q].fa = a[cur].fa = nq;
            while(p && a[p].chd[c] == q) {
                a[p].chd[c] = nq;
                p = a[p].fa;
            }
        }
    }
    last = cur;
}

int ans;
string s, t;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> s >> t;

    for(int i = 0; i < s.size(); i++) {
        insert(s[i] - 'a');
    }

    int cur = 1, clen = 0;
    for(int i = 0; i < t.size(); i++) {
        while(cur > 1 && !a[cur].chd[t[i] - 'a']) {
            cur = a[cur].fa;
            clen = a[cur].len;
        }
        if(a[cur].chd[t[i] - 'a']) cur = a[cur].chd[t[i] - 'a'], ++clen;
        ans = max(ans, clen);
    }

    cout << ans << endl;

    return 0;
}

P6640 [BJOI2020] 封印

题意

给出只包含小写字母 \(a,b\) 的两个字符串 \(s,t\)，\(q\) 次询问，每次询问 \(s[l,r]\) 和 \(t\) 的最长公共子串长度。

\(|s|,|t|\le 2\times 10^5,\ q\le 2\times 10^5\)

如果我们对 \(s\) 建立 SAM，则每次查询都需要遍历一遍 \(t\)，求出 \(t\) 的所有前缀的匹配长度和位置，然后查询 \(\operatorname{endpos}\) 和 \([l+len-1,r]\) 的交。时间复杂度太大，不能通过本题。

我们先将问题弱化，每次查询保证 \(l=1\)，即查询 \(s\) 的一个前缀和 \(t\) 的最长公共子串。此时我们可以对 \(t\) 建立 SAM，即可线性预处理出 \(s[1,i]\) 和 \(t\) 的最长公共子串（必须包含 \(s[i]\)）长度 \(f_i\)，并通过前缀 \(\max\) 实现 \(O(1)\) 查询。

考虑 \(l\ne 1\) 的情况。考察分讨弱化版中统计到的子串：

  • 对于 \(i<l\) 的串一定完全不合法；
  • 对于 \(i-f_i+1<l\) 的串，贡献被限制为 \(i-l+1\)；
  • 对于 \(i-f_i+1\ge l\) 的串，贡献为 \(f_i\)。

形式化的说，就是要求 \(\max_{i\in [l,r]}\{\min(f_i,\ i-l+1)\}\)。

如果我们能找到第 \(2\) 种情况和第 \(3\) 种情况的分界线，就可以很快的求出答案。容易发现 \(i-f_i+1\) 是具有单调性的，因此我们可以二分得到分界点，然后用 RMQ 求出 \(\max_{i\in[p,r]}{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
 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
#include<iostream>
#include<cstring>
using namespace std;
const int N = 4E5 + 10;
const int LOGN = 20;
const int INF = (int)0x3f3f3f3f3f3f3f3f;

struct Node {
    int chd[26];
    int fa, len;
    inline Node() {
        for(int i = 0; i < 26; i++) chd[i] = 0;
        fa = len = 0;
    }
} a[N];
int nn = 1;
int last = 1;

void insert(int c) {
    int cur = ++nn, p = last;
    a[cur].len = a[p].len + 1;
    while(p && !a[p].chd[c]) {
        a[p].chd[c] = cur;
        p = a[p].fa;
    }
    if(!p) {
        a[cur].fa = 1;
    } else {
        int q = a[p].chd[c];
        if(a[q].len == a[p].len + 1) {
            a[cur].fa = q;
        } else {
            int nq = ++nn;
            a[nq].len = a[p].len + 1;
            for(int i = 0; i < 26; i++) a[nq].chd[i] = a[q].chd[i];
            a[nq].fa = a[q].fa;
            a[q].fa = a[cur].fa = nq;
            while(p && a[p].chd[c] == q) {
                a[p].chd[c] = nq;
                p = a[p].fa;
            }
        }
    }
    last = cur;
}

string s, t;

int q;
int len[N], pos[N];

namespace st {
    int lg[N];
    int mx[N][LOGN];
    void init() {
        for(int i = 2; i <= s.size(); i++) {
            lg[i] = lg[i >> 1] + 1;
        }
        for(int i = 0; i < s.size(); i++) {
            mx[i][0] = len[i];
        }
        for(int j = 1; j < LOGN; j++) {
            for(int i = 0; i + (1 << j) - 1 < s.size(); i++) {
                mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int get_max(int l, int r) {
        if(l > r) return 0;
        int d = lg[r - l + 1];
        return max(mx[l][d], mx[r - (1 << d) + 1][d]);
    }
}

int main() {

    cin >> s >> t >> q;
    for(int i = 0; i < t.size(); i++) {
        insert(t[i] - 'a');
    }
    for(int i = 0, cur = 1, clen = 0; i < s.size(); i++) {
        while(cur != 1 && !a[cur].chd[s[i] - 'a']) cur = a[cur].fa, clen = a[cur].len;
        if(a[cur].chd[s[i] - 'a']) cur = a[cur].chd[s[i] - 'a'], ++clen;
        len[i] = clen;
        pos[i] = i - clen + 1;
    }

    st::init();

    while(q--) {
        int ql, qr;
        cin >> ql >> qr;
        --ql, --qr;
        int l = ql, r = qr + 1;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(pos[mid] < ql) l = mid + 1;
            else r = mid;
        }
        cout << max(l - ql, st::get_max(l, qr)) << '\n';
    }

    return 0;
}

另一种做法是二分答案。如果 \(mid\) 合法，则要求 \(i-l+1\ge mid\) 和 \(f_i\ge mid\) 同时满足。第一个条件等价于 \(i\ge mid+l-1\)，第二个条件直接使用 st 表查询 \(i\in[mid+l-1,r]\) 的 \(f_i\) 的最值即可。

技巧

形如 \(\max\{\min\{???\}\}\) 或 \(\min\{\max\{???\}\}\)（不要求 \(\max\) 和 \(\min\) 有枚举变量 \(i\)），可以考虑使用二分答案解决。

CF1037H Security

题意

给定字符串 \(s\)，有 \(q\) 次询问，每次询问给定整数 \(l,r\) 和字符串 \(t\)。求字典序最小的 \(s[l,r]\) 的子串 \(s_1\)，满足 \(s_1\) 的字典序严格大于 \(t\)。求字典序最小的 \(s_1\)。

若无解，输出 \(-1\)。

容易发现，\(s_1\) 一定是 \(t\) 的一个真前缀再添加一个字典序更大的字符得到。因此我们枚举这个前缀，并且试填后一个字符，使用线段树合并维护 \(\operatorname{endpos}\) 集合，判断 \(s\) 是否包含这个子串即可。

代码 
  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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<iostream>
using namespace std;
const int N = 2E5 + 10;
const int LOGN = 20;

struct Edge {
    int v, next;
} pool[N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

struct Node {
    int chd[26];
    int fa, len;
} a[N];
int nn = 1;
int last = 1;

int n;

int rt[N];
namespace SegT {
    int sum[2 * N * LOGN], chd[2 * N * LOGN][2];
    int nn;
    void insert(int &p, int l, int r, int q) {
        if(!p) p = ++nn;
        sum[p]++;
        if(l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        if(q <= mid) insert(chd[p][0], l, mid, q);
        else insert(chd[p][1], mid + 1, r, q);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(!p) return 0;
        if(ql <= l && r <= qr) {
            return sum[p];
        }
        int mid = (l + r) >> 1;
        if(mid >= qr) return query(chd[p][0], l, mid, ql, qr);
        if(mid < ql) return query(chd[p][1], mid + 1, r, ql, qr);
        return query(chd[p][0], l, mid, ql, qr) + query(chd[p][1], mid + 1, r, ql, qr);
    }
    int merge(int &p1, int &p2, int l, int r) {
        if(!p1 || !p2) {
            return p1 | p2;
        }
        int p = ++nn;
        sum[p] = sum[p1] + sum[p2];
        if(l == r) {
            return p;
        }
        int mid = (l + r) >> 1;
        chd[p][0] = merge(chd[p1][0], chd[p2][0], l, mid);
        chd[p][1] = merge(chd[p1][1], chd[p2][1], mid + 1, r);
        return p;
    }
}

int cnt = 0;
void insert(int c) {
    int cur = ++nn, p = last;
    a[cur].len = a[p].len + 1;
    SegT::insert(rt[cur], 1, n, a[cur].len);
    while(p && !a[p].chd[c]) {
        a[p].chd[c] = cur;
        p = a[p].fa;
    }
    if(!p) {
        a[cur].fa = 1;
    } else {
        int q = a[p].chd[c];
        if(a[q].len == a[p].len + 1) {
            a[cur].fa = q;
        } else {
            int nq = ++nn;
            a[nq].len = a[p].len + 1;
            for(int i = 0; i < 26; i++) a[nq].chd[i] = a[q].chd[i];
            a[nq].fa = a[q].fa;
            a[q].fa = a[cur].fa = nq;
            while(p && a[p].chd[c] == q) {
                a[p].chd[c] = nq;
                p = a[p].fa;
                ++cnt;
            }
        }
    }
    last = cur;
}

void dfs(int u) {
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        dfs(v);
        rt[u] = SegT::merge(rt[u], rt[v], 1, n);
    }
}

bool check(int st, int l, int r, int len) {
    if(st <= 1) return 0;
    return SegT::query(rt[st], 1, n, l + len - 1, r);
}

string s, t;
int q, l, r;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> s >> q;
    n = s.size();
    for(int i = 0; i < n; i++) insert(s[i] - 'a');
    for(int i = 2; i <= nn; i++) addEdge(a[i].fa, i);
    dfs(1);

    while(q--) {
        cin >> l >> r >> t;
        t += (char)('a' - 1);
        int cur = 1;
        int ans1 = -1, ans2;
        for(int i = 0; i < (int)t.size(); i++) {
            for(int j = t[i] - 'a' + 1; j < 26; j++) {
                if(check(a[cur].chd[j], l, r, i + 1)) {
                    ans1 = i;
                    ans2 = j;
                    break;
                }
            }
            if(!a[cur].chd[t[i] - 'a']) break;
            cur = a[cur].chd[t[i] - 'a'];
        }
        if(~ans1) {
            if(ans1) cout << t.substr(0, ans1);
            cout << (char)(ans2 + 'a') << '\n';
        } else cout << -1 << endl;
    }

    if(cnt > 2 * n) throw -1;

    return 0;
}

CF1063F String Journey

题意

给定一个长度为 \(n\) 的字符串 \(s\)，请你选出它的一个子串序列 \(t_1,t_2,\cdots t_k\)，满足 \(t_1\sim t_k\) 在 \(s\) 中按顺序且不重叠的出现，并且 \(\forall i\in [2,n]\)，\(t_{i}\) 在 \(t_{i-1}\) 中出现过。请你求出最大的 \(k\)。

\(n\le 5\times 10^5\)

先将字符串翻转，序列的约束变为 \(t_{i-1}\) 在 \(t_i\) 中出现过，答案不变。不难注意到，钦定 \(t_i\) 恰好比 \(t_{i-1}\) 多一个字符一定不劣。

考虑 dp，设 \(f_i\) 表示 \(s\) 的 \([1,i]\) 前缀的答案，并且钦定 \(t_k\) 的末尾必须是 \(s_i\)。我们注意到，\(t_k\) 匹配的起始位置，也就是 \(i-f_i+1\) 是单调不降的（容易导出和最优性矛盾）。

这起始我们可以使用双指针辅助我们的转移。记 \([l,r]\) 表示 \(t_k\) 的位置，我们枚举 \(r\)，并处理出最小的 \(l\)。当前 \(l\) 合法的充要条件是 \([l+1,r],[l,r-1]\) 之一在 \([1,l-1]\) 里面出现过，并且存在一个对应的 dp 值不低于 \(r-l\)。

考虑建出 \(s\) 的 SAM 用来优化匹配、转移的过程。我们用 \(g_u\) 表示在 \([1,l-1]\) 前缀中，\(u\) 等价类的所有 \(\operatorname{endpos}\) 位置 \(f_i\) 的最大值。当 l++ 时，我们动态更新 \(g_u\) 即可。

优化连续段 dp 时，应该注意观察其连续段的左端点是否具有单调性。这样，我们就可以使用双指针进行处理。

完整代码 
 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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;

struct Node {
    int chd[26];
    int fa, len;
    inline Node() {
        for(int i = 0; i < 26; i++) chd[i] = 0;
        fa = len = 0;
    }
} a[N];
int nn = 1, last = 1;

void insert(int c) {
    int cur = ++nn, p = last;
    a[cur].len = a[p].len + 1;
    last = cur;
    while(p && !a[p].chd[c]) {
        a[p].chd[c] = cur;
        p = a[p].fa;
    }
    if(!p) {
        a[cur].fa = 1;
        return;
    }
    int q = a[p].chd[c];
    if(a[q].len == a[p].len + 1) {
        a[cur].fa = q;
        return;
    }
    int nq = ++nn;
    a[nq].len = a[p].len + 1;
    for(int i = 0; i < 26; i++) a[nq].chd[i] = a[q].chd[i];
    a[nq].fa = a[q].fa;
    a[q].fa = a[cur].fa = nq;
    while(p && a[p].chd[c] == q) {
        a[p].chd[c] = nq;
        p = a[p].fa;
    }
}

int n, ans;
string s;

int sta[N];
int f[N], g[N];

int main() {

    cin >> n >> s;
    reverse(s.begin(), s.end());
    for(int i = 0; i < n; i++) insert(s[i] - 'a');

    int cur = 1, pre = 1;
    for(int l = 0, r = 0; r < n; r++) {
        pre = cur;
        cur = a[cur].chd[s[r] - 'a']; // 由于 SAM 就是用 s 建出来的，因此一定有匹配边
        while(l < r) {
            if(max(g[pre], max(g[a[cur].fa], g[cur])) >= r - l) break;
            // 三个数取最大值的原因是：如果 cur 是等价类中最短的一个，那么 [l+1,r] 就在 link[cur] 等价类中
            // 同时由于是取 max，因此我们直接用 max(g[link[cur]], g[cur]) 取 max 来表示 [l+1,r] 的出现位置的 dp 值

            // 否则 l++，加入 f[l] 的贡献
            if(f[l] > g[sta[l]]) {
                g[sta[l]] = f[l];
                int p = a[sta[l]].fa;
                // sta[l] 的后缀会被包含在 [l-f[l]+1,l] 中，因此其 dp 值的贡献等于等价类的长度
                while(p && g[p] < a[p].len) {
                    g[p] = a[p].len;
                    p = a[p].fa;
                }
            }
            ++l;
            // 如果等价类变化，就跳 link
            if(a[a[cur].fa].len >= r - l + 1) cur = a[cur].fa;
            if(a[a[pre].fa].len >= r - l) pre = a[pre].fa;
        }
        // 记录状态节点和 dp 值
        sta[r] = cur;
        f[r] = r - l + 1;
        ans = max(ans, f[r]);
    }

    cout << ans << endl;

    return 0;
}

CF700E Cool Slogans

题意

给你一个长为 \(n\) 的字符串 \(s\)，请你求出一个最长的字符串序列 \(t_1,t_2\cdots t_k\) 满足 \(t_i\) 都是 \(s\) 的子串，并且 \(\forall i\in [2,k]\)，\(t_{i-1}\) 都至少在 \(t_i\) 中出现了两次。

\(n\le 2\times 10^5\)

首先我们注意到一个性质：钦定所有 \(t_{i-1}\) 都是 \(t_i\) 的 border，一定不劣。

这样做的一个必要条件是，\(t_{i-1}\) 是 \(t_i\) 的一个后缀。同时注意到：对于 \(i\ne j\)，\(t_i\) 和 \(t_j\) 一定不在同一个等价类内（否则会循环到字符串左端，产生矛盾）。因此，\(t\) 序列形如 \(\operatorname{link}\) 树的一条根链的子序列。

同时，得益于 \(\operatorname{endpos}\) 等价类优秀的性质，我们将 \(t\) 中的所有子串都替换为等价类中最长的一个，仍然合法。

我们在 \(\operatorname{link}\) 树上 dp，从父亲向儿子转移，能选则选的贪心策略是不劣的。判断是否出现两次的过程中需要用到 \(\operatorname{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
 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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<iostream>
#include<cstring>
using namespace std;
const int N = 4e5 + 10;
const int LOGN = 20;

struct Edge {
    int v, next;
} pool[N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int rt[N];
namespace SegT {
    int nn;
    int sum[N * LOGN], chd[N * LOGN][2];
    inline void push_up(int p) {
        sum[p] = sum[chd[p][0]] + sum[chd[p][1]];
    }
    void insert(int &p, int l, int r, int q) {
        if(!p) p = ++nn;
        if(l == r) {
            ++sum[p];
            return;
        }
        int mid = (l + r) >> 1;
        if(q <= mid) insert(chd[p][0], l, mid, q);
        else insert(chd[p][1], mid + 1, r, q);
        ++sum[p];
    }
    int merge(int x, int y, int l, int r) {
        if(!x || !y) return x | y;
        if(l == r) throw;
        int cur = ++nn;
        int mid = (l + r) >> 1;
        chd[cur][0] = merge(chd[x][0], chd[y][0], l, mid);
        chd[cur][1] = merge(chd[x][1], chd[y][1], mid + 1, r);
        push_up(cur);
        return cur;
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(!p) return 0;
        if(ql <= l && r <= qr) return sum[p];
        int mid = (l + r) >> 1;
        if(qr <= mid) return query(chd[p][0], l, mid, ql, qr);
        if(mid < ql) return query(chd[p][1], mid + 1, r, ql, qr);
        return query(chd[p][0], l, mid, ql, qr) + query(chd[p][1], mid + 1, r, ql, qr);
    }
    void print(int p, int l, int r) {
        if(!p) return;
        if(l == r) {
            cout << l << ' ';
            return;
        }
        int mid = (l + r) >> 1;
        print(chd[p][0], l, mid);
        print(chd[p][1], mid + 1, r);
    }
}

// max{endpos}
int mxp[N];

struct Node {
    int chd[26];
    int fa, len;
    inline Node() {
        for(int i = 0; i < 26; i++) chd[i] = 0;
        fa = len = 0;
    }
} a[N];
int nn = 1, last = 1;

int n;
string s;

void insert(char c) {
    int cur = ++nn, p = last;
    last = cur;
    a[cur].len = a[p].len + 1;
    mxp[cur] = a[cur].len;
    SegT::insert(rt[cur], 1, n, a[cur].len);
    while(p && !a[p].chd[c]) {
        a[p].chd[c] = cur;
        p = a[p].fa;
    }
    if(!p) {
        a[cur].fa = 1;
    } else {
        int q = a[p].chd[c];
        if(a[q].len == a[p].len + 1) {
            a[cur].fa = q;
        } else {
            int nq = ++nn;
            a[nq].len = a[p].len + 1;
            for(int i = 0; i < 26; i++) a[nq].chd[i] = a[q].chd[i];
            a[nq].fa = a[q].fa;
            a[q].fa = a[cur].fa = nq;
            while(p && a[p].chd[c] == q) {
                a[p].chd[c] = nq;
                p = a[p].fa;
            }
        }
    }
}

// 判断节点 y 是否在 x 中出现了两次及以上
bool check(int x, int y) {
    return (bool)SegT::query(rt[y], 1, n, mxp[x] - a[x].len + a[y].len, mxp[x] - 1);
}

int ans;
int f[N], pre[N];

void dfs1(int u) {
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        dfs1(v);
        rt[u] = SegT::merge(rt[u], rt[v], 1, n);
        mxp[u] = max(mxp[u], mxp[v]);
    }
}

void dfs2(int u) {
    ans = max(ans, f[u]);
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(u != 1) {
            if(check(v, pre[u])) {
                f[v] = f[u] + 1;
                pre[v] = v;
            } else {
                f[v] = f[u];
                pre[v] = pre[u];
            }
        } else {
            f[v] = 1;
            pre[v] = v;
        }
        dfs2(v);
    }
}

int main() {

    cin >> n >> s;
    s = '#' + s;

    for(int i = 1; i <= n; i++) insert(s[i] - 'a');
    for(int i = 2; i <= nn; i++) addEdge(a[i].fa, i);

    dfs1(1);
    dfs2(1);

    cout << ans << '\n';

    return 0;
}

P4770 [NOI2018] 你的名字

题意

给定一个字符串 \(s\)。有 \(q\) 次询问，每次询问给定一个字符串 \(t\) 和 \(l,r\)，表示询问 \(t\) 有多少个本质不同的子串满足其在 \(s[l,r]\) 中没有出现过。

\(|s|\le 5\times 10^5,\ \sum |t|\le 10^6\)

对于一个 \(t\)，考虑先求出 \(f_i\) 表示 \(t\) 的 \([1,i]\) 前缀在 \(s[l,r]\) 中的最长匹配后缀。然后我们建出 \(t\) 的 SAM，枚举每个等价类，统计该等价类中有多少个串是合法的。

考虑如何求出 \(f_i\)。我们先建出 \(s\) 的 SAM，然后把 \(t\) 放上去跑，如果失配就一个一个往前跳，直到 \(t[i-k+1,i]\) 在 \(s[l,r]\) 中完整的出现至少一次。其中我们需要用到 \(\operatorname{endpos}\) 集合来判断匹配，这里用线段树合并维护一下即可。

在跑 SAM 时，如果遇到失配的情况，我们通常会直接跳 \(\operatorname{link}\) 而不是一个一个前跳。其实，后者的时间复杂度没有更劣，并且可以处理一些跳 \(\operatorname{link}\) 不能处理的问题。

求出 \(f_i\) 之后，我们枚举 \(t\) 的 SAM 中的每一个等价类；我们找到这个等价类的 \(\operatorname{endpos}\) 的最大值（随便一个都可以，这里使用最大值），取它的 \(f_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
 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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#include<iostream>
#include<cstring>
#include<cassert>
#define int long long
using namespace std;
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int LOGN = 20;

struct Edge {
    int v, next;
} pool[2 * M];
int ne, head[2 * M];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

void clear_Edge(int n) {
    for(int i = 0; i <= n + 5; i++) head[i] = 0;
    ne = 0;
}

int rt[2 * N];
namespace SegT {
    int chd[2 * N * LOGN][2];
    int nn;
    void insert(int &p, int l, int r, int q) {
        if(!p) p = ++nn;
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(q <= mid) insert(chd[p][0], l, mid, q);
        else insert(chd[p][1], mid + 1, r, q);
    }
    int merge(int x, int y, int l, int r) {
        if(!x || !y) return x | y;
        if(l == r) assert(0);
        int cur = ++nn;
        int mid = (l + r) >> 1;
        chd[cur][0] = merge(chd[x][0], chd[y][0], l, mid);
        chd[cur][1] = merge(chd[x][1], chd[y][1], mid + 1, r);
        return cur;
    }
    bool query(int p, int l, int r, int ql, int qr) {
        if(!p) return 0;
        if(ql <= l && r <= qr) return 1;
        int mid = (l + r) >> 1;
        if(qr <= mid) return query(chd[p][0], l, mid, ql, qr);
        if(mid < ql) return query(chd[p][1], mid + 1, r, ql, qr);
        return query(chd[p][0], l, mid, ql, qr) || query(chd[p][1], mid + 1, r, ql, qr);
    }
    void print(int p, int l, int r) {
        if(!p) return;
        if(l == r) { cout << l << ' '; return; }
        int mid = (l + r) >> 1;
        print(chd[p][0], l, mid);
        print(chd[p][1], mid + 1, r);
    }
}

int n, m, q;
int l, r;
int f[N];

template<int N>
struct SAM {
    struct Node {
        int chd[26];
        int fa, len;
        inline void clear() {
            for(int i = 0; i < 26; i++) chd[i] = 0;
            fa = len = 0;
        }
    } a[2 * N];
    int nn = 1, last = 1;
    void insert(int c) {
        int cur = ++nn, p = last;
        a[cur].clear();
        a[cur].len = a[p].len + 1;
        pt[a[cur].len] = cur;
        last = cur;
        while(p && !a[p].chd[c]) {
            a[p].chd[c] = cur;
            p = a[p].fa;
        }
        if(!p) {
            a[cur].fa = 1;
        } else {
            int q = a[p].chd[c];
            if(a[q].len == a[p].len + 1) {
                a[cur].fa = q;
            } else {
                int nq = ++nn;
                a[nq].clear();
                a[nq].len = a[p].len + 1;
                for(int i = 0; i < 26; i++) a[nq].chd[i] = a[q].chd[i];
                a[nq].fa = a[q].fa;
                a[q].fa = a[cur].fa = nq;
                while(p && a[p].chd[c] == q) {
                    a[p].chd[c] = nq;
                    p = a[p].fa;
                }
            }
        }
    }
    // s1
    int pt[N];
    void dfs1(int u) {
        for(int e = head[u]; e; e = pool[e].next) {
            int v = pool[e].v;
            dfs1(v);
            rt[u] = SegT::merge(rt[u], rt[v], 1, n);
        }
    }
    void init_SegT() {
        clear_Edge(nn);
        for(int i = 1; i <= n; i++) SegT::insert(rt[pt[i]], 1, n, i); 
        for(int i = 2; i <= nn; i++) addEdge(a[i].fa, i);
        dfs1(1);
    }
    void trans(int &cur, int &len, int c) {
        while(cur) {
            if(a[cur].chd[c] && SegT::query(rt[a[cur].chd[c]], 1, n, l + len, r)) {
                ++len;
                cur = a[cur].chd[c];
                return;
            }
            --len;
            if(len <= a[a[cur].fa].len) cur = a[cur].fa;
        }
        cur = 1;
        len = 0;
        return;
    }
    // s2
    int mxp[M];
    void clear() {
        for(int i = 1; i <= nn; i++) a[i].clear();
        nn = last = 1;
    }
    void dfs2(int u) {
        for(int e = head[u]; e; e = pool[e].next) {
            int v = pool[e].v;
            dfs2(v);
            mxp[u] = max(mxp[u], mxp[v]);
        }
    }
    int calc() {
        clear_Edge(nn);
        for(int i = 1; i <= nn; i++) mxp[i] = 0;
        for(int i = 1; i <= m; i++) mxp[pt[i]] = i;
        for(int i = 2; i <= nn; i++) addEdge(a[i].fa, i);
        dfs2(1);
        int res = 0;
        for(int i = 2; i <= nn; i++) {
            int l1 = a[i].len, l2 = a[a[i].fa].len;
            if(f[mxp[i]] >= l1) continue;
            if(f[mxp[i]] <= l2) res += l1 - l2;
            else res += l1 - f[mxp[i]];
        }
        return res;
    }
};

SAM<N> s1;
SAM<M> s2;

string s, t;

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> s >> q;
    n = s.size();

    for(int i = 0; i < n; i++) {
        s1.insert(s[i] - 'a');
    }
    s1.init_SegT();

    while(q--) {
        cin >> t >> l >> r;
        m = t.size();
        int cur = 1, len = 0;
        for(int i = 0; i < m; i++) {
            s1.trans(cur, len, t[i] - 'a');
            f[i + 1] = len;
        }
        for(int i = 0; i < m; i++) s2.insert(t[i] - 'a');
        cout << s2.calc() << '\n';
        s2.clear();
    }

    return 0;
}

P3735 [HAOI2017] 字符串

请见 ACAM。