后缀自动机板子

$\dagger$ 约定 $S_{[l,r]}$ 表示字符串 $S$ 取出下标为 $[l,r]$ 的部分组成的字符串。

$\textrm{Example}\ 1$

NOI2008

题目描述

给定字符串 $S$ 以及 $Q$ 次询问。

每次询问给出串 $T$ 和下标 $l,r(1\leq l\leq r\leq |S|)$，设 $S’$ 为 $S$ 取下标 $[l,r]$ 的一段字符。

求满足在 $T$ 中出现且不在 $S’$ 中出现的字符串个数。

$|S|\leq 5\times 10^5, Q \leq 10^5, \sum |T| \leq 10^6$

题解

将答案拆为求 $T$ 本质不同子串个数和 $T$ 与 $S’$ 公共子串个数。

先假设 $l=1,r=\left | S \right |$，建出 $S$ 的后缀自动机，然后扫描字符串 $T$。

设 $h_j$ 表示满足 $T_{[j-len+1,j]}$ 为 $S$ 的子串的最大的 $len$。

定义 $p$ 表示现在在 $S$ 的后缀自动机上的哪个节点，扫描 $T$ 并依次进行如下操作：

1. $c := T_i$
2. 重复执行 $p=link(p)$，直到 $p.to[c] \ne NULL$
3. $p\gets p.to[c]$

我们证明如上操作的复杂度，每次执行 $3$ 操作， $len$ 会加一，而执行 $2$ 操作，$len$ 会至少减一，所以均摊 $O(\left | T\right |)$。

得到 $h_i$ 后，我们在 $T$ 的后缀自动机上找到 $T_{[i-h_i+1, i]}$ 的等价类 $v$，则 $v$ 以及 $v$ 在后缀链接上的祖先节点中，所有 $len \leq h_i$ 的字符串都满足同时为 $S,T$ 的子串。

所以我们现在 $v$ 上更新 $g_v \gets \max(g_v, h_i)$，完成所有 $n$ 个更新后，对后缀链接建图，$dfs$ 一边这棵树即可。

时间复杂度 $O(|S|+\sum |T|)$。

接下来，我们需要求的是 $S_{[l,r]}$ 的后缀自动机，根据以上解法，我们需要的是：

1. 爬父节点；
2. 查询 $p.to[c]$。

先拿出整个串的后缀自动机，定义一些点为虚点，这些点满足没有任何一个串为 $T_{[l,r]}$ 的子串。

我们发现如果 $u$ 不为虚点，那么 $u$ 的后缀链接也不为虚点，于是我们只需要在整串的自动机基础上删除虚点即可。

但这样效率太低，所以我们只需要查询 $p.to[c]$ 时，$check$ 这个点，那么如何 $check$ ？

我们预处理出后缀自动机的 $endpos$ 集合，点 $u$ 的 $endpos$ 集合即为后缀树上 $u$ 的所有儿子节点 $endpos$ 集合的并集。

初始化为对于所有 $j$，找到前缀 $S_{[1,j]}$ 的等价类，然后这个节点将 $j$ 加入 $endpos$，当然这个节点不一定为叶子节点。

维护 $endpos$ 集合，我们需要用到 线段树合并，并且需要在合并时加入可持久化。

$check$ 时，找到 $u$ 的第一个小于等于 $r$ 的 $endpos$，然后根据最小长度判断。

总复杂度 $O((|S| + \sum |T|) \log |S|)$。

总结

本题出现技巧主要有求两个串的公共子串个数和模拟某个子串的后缀自动机。

#include <bits/stdc++.h>
#define pb push_back
#define ll long long

using namespace std;

const int N = 4e6 + 10, B = 2e7 + 10;
char s[N / 4];
int n, h[N], e[N], ne[N], idx;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int treetot, root[N / 2];
struct Ciallo {
    int ans, l, r;
} tr[B];

void modify(int &u, int l, int r, int x) {
    if (!u) u = ++ treetot;
    tr[u].ans = max(tr[u].ans, x);
    if (l == r) return;
    int mid = l + r >> 1;
    if (x <= mid) modify(tr[u].l, l, mid, x);
    else modify(tr[u].r, mid + 1, r, x);
}

int query(int u, int l, int r, int s, int t) {
    if (!u) return 0;
    if (s <= l && r <= t) return tr[u].ans;
    int mid = l + r >> 1;
    if (s > mid) return query(tr[u].r, mid + 1, r, s, t);
    if (t <= mid) return query(tr[u].l, l, mid, s, t);
    return max(query(tr[u].l, l, mid, s, t), query(tr[u].r, mid + 1, r, s, t));
} 

int merge(int x, int y, int l, int r) {
    if (!x || !y) return x | y;
    if (l > r) return 0;
    int z = ++ treetot;
    tr[z].ans = max(tr[x].ans, tr[y].ans);
    int mid = l + r >> 1;
    tr[z].l = merge(tr[x].l, tr[y].l, l, mid);
    tr[z].r = merge(tr[x].r, tr[y].r, mid + 1, r);
    return z;
}

int tot = 0;
struct Node {
    int ch[26], fa, len;
} node[N];

int check(int u, int l, int r) {
    int rr = query(root[u], 1, n, 1, r);
    if (rr - node[node[u].fa].len >= l) return min(rr - l + 1, node[u].len);
    return 0;
}

struct suffix_automaton {
    int rt = ++ tot, last = rt;
    vector<int> vec = {rt};
    void extend(int c) {
        int p = last, np = last = ++ tot;
        node[np].len = node[p].len + 1;
        vec.pb(np);
        for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
        if (!p) node[np].fa = rt;
        else {
            int q = node[p].ch[c];
            if (node[q].len == node[p].len + 1) node[np].fa = q;
            else {
                int nq = ++ tot;
                vec.pb(nq);
                node[nq] = node[q], node[nq].len = node[p].len + 1;
                node[q].fa = node[np].fa = nq;
                for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
            }
        }
    }
    void addedge() {
        for (int i : vec) {
            if (node[i].fa)
                add(node[i].fa, i);
        }
    }
} S, T[100010];

int lmx[N];

long long dfs(int u) {
    long long ans = 0; 
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        ans += dfs(j);
        lmx[u] = max(lmx[u], lmx[j]);
    }
    int l = node[node[u].fa].len + 1, r = node[u].len;
    if (lmx[u] >= l) ans += r - min(lmx[u], r);
    else ans += r - l + 1;
    return ans;
} 

void dfs2(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs2(j);
        root[u] = merge(root[u], root[j], 1, n);
    }
}

int main() {
    node[0].len = -1;
    memset(h, -1, sizeof h); 
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i ++ ) S.extend(s[i] - 'a');
    S.addedge();
    int p = S.rt;
    for (int i = 1; i <= n; i ++ ) {
        int c = s[i] - 'a';
        p = node[p].ch[c];
        modify(root[p], 1, n, i);
    }
    dfs2(S.rt);
    int Q;
    scanf("%d", &Q);
    for (int id = 0; id < Q; id ++ ) {
        string t;
        cin >> t;
        int l, r;
        scanf("%d%d", &l, &r);
        for (int i = 0; i < t.size(); i ++ ) T[id].extend(t[i] - 'a');
        T[id].addedge();
        int p1 = S.rt, p2 = T[id].rt, le = 0;
        for (int i = 0; i < t.size(); i ++ ) {
            int c = t[i] - 'a';
            for (; p1; p1 = node[p1].fa) {
                if (node[p1].ch[c]) {
                    int q = node[p1].ch[c];
                    int h = check(q, l, r);
                    if (node[node[p1].fa].len + 2 <= h) {
                        le = min(le + 1, h);
                        break;
                    }
                }
                le = node[node[p1].fa].len;
            }
            if (!p1) p1 = S.rt, le = 0;
            else p1 = node[p1].ch[c];
            p2 = node[p2].ch[c];
            lmx[p2] = max(lmx[p2], le);
        }
        printf("%lld\n", dfs(T[id].rt));
    }
    return 0;
}

$\textrm{Example}\ 2$

CF666E

题目描述

给定串 $S$ 和 $m$ 个串 $T_1, T_2, \cdots , T_m$，$Q$ 次询问，每次给出 $l,r,pl,pr$，

求 $S_{[pl,pr]}$ 在 $T_{l}, \cdots, T_{r}$ 哪个串中出现次数最多,若有一样多的，取最左边的。

$1\leq |S|, q \leq 5\times 10^5, \sum |T| \leq 5\times 10^4$。

题解

对于 $T$ 建广义后缀自动机，对于自动机上的一点，建一个线段树，维护 $T_1, T_2, \cdots , T_m$ 中该点字符串最大出现的次数，同时维护出现次数最多的编号最小的位置。

很显然对于同一个等价类的一列字符串，它们在 $T$ 的出现次数都是相同的。

那么如何求这个线段树？考虑线段树合并，初始时在 $T_i$ 中的每一个前缀的所属等价类的线段树第 $i$ 个位置上加 $1$，然后计算线段树 $u$ 时合并上 $u$ 在后缀树上儿子节点 $v$ 的线段树。

最后的问题是如何求 $S_{[pl,pr]}$ 在自动机上的等价类，首先预处理 $S$ 的前缀 $S_{[1,i]}$ 的最长后缀满足这个后缀在自动机上存在，设这个等价类为 $pos_i$。

然后 $dfs$ 一遍后缀树并倍增求出 $f_{i,j}$ 表示节点 $i$ 在自动机上跳 $2^j$ 次父节点后所在的点。

最后在 $pos_{pr}$ 的基础上倍增求出 $S_{[pl,pr]}$ 所属节点。

总时间复杂度 $O(n\log n)$。

$\textrm{Submission}$