VEXOBEN
Vexoben
Mar 14, 2019
It takes 12 minutes to read this article.

题目链接: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;
}