跳转至

后缀自动机（Suffix Automaton, SAM）

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

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

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

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\) 。

对于一个等价类 \(w\)，记其中最长的子串为 \(longest\)，长度为 \(len\)；最短的子串长度为 \(minlen\)。

\(\operatorname{endpos}\) 等价类有如下性质：

  • 两个子串的 \(\operatorname{endpos}\) 集合要么不交，要么包含，因为 \(\operatorname{endpos}\) 具有包含关系的两个子串 \(t_1,t_2\) 一定具有后缀关系；
  • 对于同一 \(\operatorname{endpos}\) 等价类的任一两个子串，较短者为较长者的后缀，且该等价类中的子串长度恰好覆盖一个区间 \([\operatorname{minlen},\operatorname{len}]\)。

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

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

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

线性求 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\) 即可。

完整代码 
 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 - Longest Common Substring

题意

输入两个字符串 \(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

CF700E Cool Slogans