Vexoben
Mar 14, 2019
题目链接：NOI2018 你的名字
题意
给定字符串，组询问，每次给定一个字符串和整数 ，问出现在但不出现在中的本质不同字符串数目。
数据范围：
题解
补集转化一下，就是求中本质不同字符串减去和中都出现的本质不同字符串数目。
对和分别建一个后缀自动机。设为在上出现的最长后缀。的后缀自动机上，一个节点的集合最靠右的位置是，那么这个节点对答案的贡献就是
也就是这个节点本身本质不同的子串数和它能在上匹配的子串数取
接着考虑如何求出。我们可以先无视的限制，求出在上能匹配的最长后缀。这直接像AC自动机一样跳，只是用树边代替边。假设匹配出来的最长字符串是，我们不断删去的第一个字符，使得它在上出现即可，也即是对当前节点判断集合是否包含中的数，线段树合并可以轻易地解决这个问题。
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int N = 1e6 + 10;
template <typename T> void read(T &x) {
int f = 0;
char c = getchar();
while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
for (x = 0; c >= '0' && c <= '9'; c = getchar())
x = x * 10 - '0' + c;
if (f) x = -x;
}
char s[N];
int n, q, m, res[N];
vector<int> vec[N];
namespace SegTree {
int tot, tr[N * 50], ch[N * 50][2];
void Upd(int &x, int l, int r, int pos) {
if (!x) x = ++tot;
++tr[x];
if (l == r) return;
int mid = (l + r) >> 1;
if (mid >= pos) Upd(ch[x][0], l, mid, pos);
if (mid < pos) Upd(ch[x][1], mid + 1, r, pos);
}
int merge(int x, int y, int l, int r) {
if (!x || !y) return x + y;
int z = ++tot;
if (l == r) {
tr[z] = tr[x] + tr[y];
return z;
}
int mid = (l + r) >> 1;
ch[z][0] = merge(ch[x][0], ch[y][0], l, mid);
ch[z][1] = merge(ch[x][1], ch[y][1], mid + 1, r);
tr[z] = tr[ch[z][0]] + tr[ch[z][1]];
return z;
}
int query(int x, int l, int r, int ql, int qr) {
if (!x || ql > qr) return 0;
if (ql <= l && r <= qr) return tr[x];
int mid = (l + r) >> 1, ans = 0;
if (ql <= mid) ans += query(ch[x][0], l, mid, ql, qr);
if (mid < qr) ans += query(ch[x][1], mid + 1, r, ql, qr);
return ans;
}
}
namespace SAM1 {
int rt = 1, las = 1, tot = 1;
int len[N], pre[N], root[N], ch[N][26];
int newnode(int l) {
++tot;
len[tot] = l;
return tot;
}
void ins(int c, int x) {
int p = las, np = las = newnode(len[p] + 1);
SegTree::Upd(root[np], 1, n, x);
while (!ch[p][c]) ch[p][c] = np, p = pre[p];
if (!p) pre[np] = rt;
else {
int q = ch[p][c], nq;
if (len[p] + 1 == len[q]) pre[np] = q;
else {
nq = newnode(len[p] + 1);
memcpy(ch[nq], ch[q], sizeof ch[q]);
pre[nq] = pre[q]; pre[np] = pre[q] = nq;
while (ch[p][c] == q) ch[p][c] = nq, p = pre[p];
}
}
}
void calc_right() {
static int cnt[N], ord[N];
for (int i = 1; i <= tot; ++i) ++cnt[len[i]];
for (int i = 1; i <= tot; ++i) cnt[i] += cnt[i - 1];
for (int i = tot; i >= 1; --i) ord[cnt[len[i]]--] = i;
for (int i = tot; i >= 1; --i) {
if (ord[i] == rt) continue;
int nw = SegTree::merge(root[ord[i]], root[pre[ord[i]]], 1, n);
root[pre[ord[i]]] = nw;
}
}
void solve(char *s, int L, int R) {
int length = strlen(s + 1);
for (int i = 1, p = 1, l = 0; i <= length; ++i) {
int c = s[i] - 'a';
while (p && !ch[p][c]) p = pre[p], l = len[p];
if (!p) {
p = rt; l = 0;
continue;
}
p = ch[p][c], ++l;
while (p > 1) {
if (SegTree::query(root[p], 1, n, L + l - 1, R)) break;
if (--l == len[pre[p]]) p = pre[p];
}
if (p == rt) continue;
for (int j = 0; j < vec[i].size(); ++j) {
res[vec[i][j]] = max(res[vec[i][j]], l);
}
}
}
}
namespace SAM2 {
int rt, tot, las;
int ch[N][26], pre[N], len[N];
void init() {
for (int i = 1; i <= tot; ++i) {
pre[i] = len[i] = res[i] = 0;
vec[i].clear();
memset(ch[i], 0, sizeof ch[i]);
}
rt = tot = las = 1;
}
int newnode(int l) {
++tot;
len[tot] = l;
return tot;
}
void ins(int c, int x) {
int p = las, np = las = newnode(len[p] + 1);
vec[x].push_back(np);
while (!ch[p][c]) ch[p][c] = np, p = pre[p];
if (!p) pre[np] = rt;
else {
int q = ch[p][c], nq;
if (len[p] + 1 == len[q]) pre[np] = q;
else {
nq = newnode(len[p] + 1);
vec[x].push_back(nq);
memcpy(ch[nq], ch[q], sizeof ch[q]);
pre[nq] = pre[q]; pre[np] = pre[q] = nq;
while (ch[p][c] == q) ch[p][c] = nq, p = pre[p];
}
}
}
long long solve() {
long long ans1 = 0, ans2 = 0;
for (int i = 1; i <= tot; ++i) {
ans1 += len[i] - len[pre[i]];
if (res[i] > len[pre[i]]) {
ans2 += min(res[i], len[i]) - len[pre[i]];
}
}
return ans1 - ans2;
}
}
int main() {
scanf("%s", s + 1), n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
SAM1::ins(s[i] - 'a', i);
}
SAM1::calc_right();
read(q);
while (q--) {
SAM2::init();
scanf("%s", s + 1), m = strlen(s + 1);
for (int i = 1; i <= m; ++i) {
SAM2::ins(s[i] - 'a', i);
}
int l, r;
read(l); read(r);
SAM1::solve(s, l, r);
printf("%lld\n", SAM2::solve());
}
return 0;
}