\(\text{P4770 [NOI2018] 你的名字 题解}\)
注意到 \(l=1,r=|S|\) 有整整 68 分的高分，让我们先来考虑这样的特殊情况。
这样的特殊情形实际上要我们求的是 \(t\) 有多少个本质不同的子串满足其不是 \(s\) 的子串。正着做看上去有些困难，于是维护 \(s,t\) 的本质不同公共子串个数，用 \(t\) 的本质不同子串个数减去即可。于是对 \(s,t\) 建出 SAM，后者是容易维护的，考虑如何维护前者。
首先我们需要知道如何匹配两个串的公共子串个数，不会的左转 OI-wiki，但这样难以解决本质不同的问题。于是我们考虑在进行匹配时顺便建出 \(t\) 的 SAM，记当前匹配的长度为 \(l\)，当前字符对应的在 \(t\) 的 SAM 上的节点是 \(p\)，那么显然在 parent 树上 \(p\) 的祖先节点会被重复计算，于是事实上该字符的贡献是 \(\max(l-\operatorname{len(link}(p)),0)\)，其中 \(\operatorname{len,link}\) 就是在 SAM 中的定义。
给出代码：
#include <bits/stdc++.h>
#define N 2000005
#define M 26
#define ll long long
using namespace std;
int n;
char s[N];
struct SuffixAutomation {
struct SAM {
int len, fa;
int s[M];
} sam[N];
int tot = 1, lst = 1;
void insert(int c) {
int p = lst, np = lst = ++tot;
sam[np].len = sam[p].len + 1;
for (; !sam[p].s[c]; p = sam[p].fa) sam[p].s[c] = np;
if (!p) sam[np].fa = 1;
else {
int q = sam[p].s[c];
if (sam[q].len == sam[p].len + 1) sam[np].fa = q;
else {
int nq = ++tot;
sam[nq] = sam[q], sam[nq].len = sam[p].len + 1;
sam[np].fa = sam[q].fa = nq;
for (; sam[p].s[c] == q; p = sam[p].fa) sam[p].s[c] = nq;
}
}
}
void init() {
for (int i = 0; i <= tot; i++) {
sam[i].len = sam[i].fa = 0;
for (int j = 0; j < 26; j++) sam[i].s[j] = 0;
}
tot = lst = 1;
}
} S, T;
ll res;
void fnd(char *s) {
int v = 1, l = strlen(s), ans = 0;
for (int i = 0; i < l; i++) {
int c = s[i] - 'a';
while (v > 1 && !S.sam[v].s[c]) {
v = S.sam[v].fa;
ans = S.sam[v].len;
}
if (S.sam[v].s[c]) {
v = S.sam[v].s[c];
++ans;
}
T.insert(c);
int p = T.lst;
res += T.sam[p].len - T.sam[T.sam[p].fa].len;
if (ans >= T.sam[T.sam[p].fa].len) res -= ans - T.sam[T.sam[p].fa].len;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> s;
int lth = strlen(s);
for (int i = 0; i < lth; i++) S.insert(s[i] - 'a');
int q;
cin >> q;
while (q--) {
cin >> s;
int l, r;
cin >> l >> r;
T.init();
res = 0;
fnd(s);
if (l == 1 && r == lth) cout << res << "\n";
}
return 0;
}
对于普遍的情形，不难发现这个式子仍然适用，不适用的是 SAM 上一些转移边是不能走的。对于询问 \((L,R)\)，如果当前匹配的长度为 \(l\)，那么某条边能走的条件就是在 \([L+l,R]\) 处有能匹配到的结尾。发现这就是 \(\operatorname{endpos}\) 集合的定义，为了尽量匹配到，我们维护区间 \(\operatorname{endpos}\) 的最大值，对于每个节点，如果其在 \([L+l,R]\) 范围内的 \(\operatorname{endpos}\) 集合是有值的，便符合条件，可以进行转移。然后线段树合并维护即可。实现时需要留意的有两个点：
- 这里的线段树合并由于不能破坏其它节点的信息，要新建节点保存信息，也就是可持久化线段树合并。
- 我们在判断的过程中会多次减小 \(l\) 的值，如果匹配不上时我们不直接跳父亲，原因是这里的判定条件和 \(l\) 的值同样是强相关的，因此每次将 \(l\) 减去 \(1\) 即可。
关于复杂度，每个字符最多会使 \(l\) 加 \(1\)，因此均摊一下是 \(O(|T|)\) 的。总的复杂度是 \(O(|S|+|T|\log |S|)\) 的。
代码：
#include <bits/stdc++.h>
#define N 2000005
#define M 26
#define ll long long
using namespace std;
char s[N];
int n;
ll res;
struct Node {
int lc, rc, mx;
} e[N << 4];
#define lc(i) e[i].lc
#define rc(i) e[i].rc
#define mx(i) e[i].mx
int cnt;
void push_up(int p) {
mx(p) = max(mx(lc(p)), mx(rc(p)));
}
void insert(int &p, int l, int r, int x) {
if (!p) p = ++cnt;
if (l == r) return mx(p) = l, void();
int mid = (l + r) >> 1;
if (x <= mid) insert(lc(p), l, mid, x);
else insert(rc(p), mid + 1, r, x);
push_up(p);
}
int mge(int p, int q, int l, int r) {
if (!p || !q) return p | q;
int np = ++cnt;
if (l == r) {
mx(np) = max(mx(p), mx(q));
return np;
}
int mid = (l + r) >> 1;
lc(np) = mge(lc(p), lc(q), l, mid);
rc(np) = mge(rc(p), rc(q), mid + 1, r);
push_up(np);
return np;
}
int query(int p, int l, int r, int ql, int qr) {
if (!p || l > r || ql > qr || l > qr || ql > r) return 0;
if (ql <= l && r <= qr) return mx(p);
int mid = (l + r) >> 1;
return max(query(lc(p), l, mid, ql, qr), query(rc(p), mid + 1, r, ql, qr));
}
int rt[N];
vector<int>v[N];
void dfs(int x) {
for (auto y : v[x]) {
dfs(y);
rt[x] = mge(rt[x], rt[y], 1, n);
}
}
struct SuffixAutomation {
int tot = 1, lst = 1;
struct SAM {
int len, fa;
int s[M];
} sam[N];
void ins(int c, int num) {
int p = lst, np = lst = ++tot;
sam[np].len = sam[p].len + 1;
for (; !sam[p].s[c]; p = sam[p].fa) sam[p].s[c] = np;
if (!p) sam[np].fa = 1;
else {
int q = sam[p].s[c];
if (sam[q].len == sam[p].len + 1) sam[np].fa = q;
else {
int nq = ++tot;
sam[nq] = sam[q], sam[nq].len = sam[p].len + 1;
sam[np].fa = sam[q].fa = nq;
for (; sam[p].s[c] == q; p = sam[p].fa) sam[p].s[c] = nq;
}
}
if (num > 0) insert(rt[lst], 1, n, num);
}
void init() {
for (int i = 0; i <= tot; i++) {
sam[i].len = sam[i].fa = 0;
for (int j = 0; j < M; j++) sam[i].s[j] = 0;
}
tot = lst = 1;
}
} S, T;
void fnd(char *s, int l, int r) {
int len = strlen(s), p = 1, ans = 0;
for (int i = 0; i < len; i++) {
int c = s[i] - 'a';
while (1) {
if (S.sam[p].s[c] && query(rt[S.sam[p].s[c]], 1, n, l + ans, r)) {
p = S.sam[p].s[c];
++ans;
break;
}
if (ans == 0) break;
--ans;
if (ans == S.sam[S.sam[p].fa].len) p = S.sam[p].fa;
}
T.ins(c, 0);
int q = T.lst;
res += T.sam[q].len - T.sam[T.sam[q].fa].len;
if (ans >= T.sam[T.sam[q].fa].len) res -= ans - T.sam[T.sam[q].fa].len;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> s;
n = strlen(s);
for (int i = 0; i < n; i++) S.ins(s[i] - 'a', i + 1);
for (int i = 2; i <= S.tot; i++) v[S.sam[i].fa].push_back(i);
dfs(1);
int q;
cin >> q;
while (q--) {
int l, r;
cin >> s >> l >> r;
T.init();
res = 0;
fnd(s, l, r);
cout << res << '\n';
}
return 0;
}