题目大意
有一个串\(S\)，每次询问给你一个串\(T\)，两个数\(L\)和\(R\)，问你\(T\)有多少个本质不同的子串不是\(S[L,R]\)的子串
SOLUTION
如果你做过生成魔咒和CF1037H，就会做这道题了
有两个坑点：
1.线段树合并时必须每次都新建结点，因为两颗树都得保留
2.每次失配时必须先尝试减小已经匹配的长度，无法继续减少时再跳\(suflink\)
我的大常数代码
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <random>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#define IINF 0x3f3f3f3f3f3f3f3fLL
#define u64 unsigned long long
#define pii pair<int, int>
#define mii map<int, int>
#define u32 unsigned int
#define lbd lower_bound
#define ubd upper_bound
#define INF 0x3f3f3f3f
#define vi vector<int>
#define ll long long
#define mp make_pair
#define pb push_back
#define is insert
#define se second
#define fi first
#define ps push
#define $SHOW(x) cout << #x" = " << x << endl
#define $DEBUG() printf("%d %s\n", __LINE__, __FUNCTION__)
using namespace std;
#define S 500000
#define Q 100000
#define T 1000000
#define mid ((l+r)>>1)
int q, n, m, L, R;
char s[S+5], t[T+5];
int nid1 = 1, lst1 = 1, ch1[26][2*S+5], link1[2*S+5], len1[2*S+5], nodecnt, root[2*S+5], ch[2][200*S+5];
int nid, lst, nxt[26][2*T+5], link[2*T+5], len[2*T+5], rest[2*T+5], val[T+5];
ll ans = 0;
int a[2*T+5], buc[2*T+5];
void add(int &o, int l, int r, int x) {
if (!o) o = ++nodecnt;
if (l == r) return ;
if (x <= mid) add(ch[0][o], l, mid, x);
else add(ch[1][o], mid+1, r, x);
}
int merge(int x, int y, int l, int r) {
int u = ++nodecnt;
if (x * y == 0) u = x ? x : y;
else {
ch[0][u] = merge(ch[0][x], ch[0][y], l, mid);
ch[1][u] = merge(ch[1][x], ch[1][y], mid + 1, r);
}
return u;
}
int query(int u, int l, int r, int L, int R) {
if (!u) return 0;
if (L <= l && r <= R) return 1;
int ret = 0;
if (L <= mid) ret |= query(ch[0][u], l, mid, L, R);
if (R > mid) ret |= query(ch[1][u], mid+1, r, L, R);
return ret;
}
void build() {
for (int i = 1, c; i <= n; ++i) {
c = s[i] - 'a';
int cur = ++nid1;
len1[cur] = len1[lst1] + 1;
add(root[cur], 1, n, i);
while (lst1 && !ch1[c][lst1]) ch1[c][lst1] = cur, lst1 = link1[lst1];
if (!lst1) link1[cur] = 1;
else {
int p = lst1, q = ch1[c][lst1];
if (len1[q] == len1[p] + 1) link1[cur] = q;
else {
int clone = ++nid1;
len1[clone] = len1[p] + 1;
for (int j = 0; j < 26; ++j) ch1[j][clone] = ch1[j][q];
link1[clone] = link1[q], link1[cur] = link1[q] = clone;
while (p && ch1[c][p] == q) ch1[c][p] = clone, p = link1[p];
}
}
lst1 = cur;
}
for (int i = 1; i <= nid1; ++i) buc[len1[i]]++;
for (int i = 1; i <= n; ++i) buc[i] += buc[i-1];
for (int i = 1; i <= nid1; ++i) a[buc[len1[i]]--] = i;
for (int i = nid1; i >= 2; --i) root[link1[a[i]]] = merge(root[link1[a[i]]], root[a[i]], 1, n);
}
void extend(int c) {
int cur = ++nid;
len[cur] = len[lst] + 1;
for(int i = 0; i < 26; ++i) nxt[i][cur] = 0;
while (lst && !nxt[c][lst]) nxt[c][lst] = cur, lst = link[lst];
if (!lst) link[cur] = 1;
else {
int p = lst, q = nxt[c][lst];
if (len[q] == len[p] + 1) link[cur] = q;
else {
int clone = ++nid;
len[clone] = len[p] + 1;
for (int i = 0; i < 26; ++i) nxt[i][clone] = nxt[i][q];
link[clone] = link[q], link[q] = link[cur] = clone;
while (p && nxt[c][p] == q) nxt[c][p] = clone, p = link[p];
}
}
lst = cur;
}
void calc() {
m = strlen(t+1);
lst = nid = 1;
int i, j, c;
for (i = 0; i < 26; ++i) nxt[i][1] = 0;
for (j = 1; j <= m; ++j) extend(t[j] - 'a');
for (i = 2; i <= nid; ++i) rest[i] = 0;
int u = 1, match = 0;
for (i = 1, c; i <= m; ++i) {
c = t[i] - 'a';
while (u && !query(root[ch1[c][u]], 1, n, L + match, R)) {
if(match > len1[link1[u]]) match--;
else u = link1[u], match = len1[u];
}
if (!u) u = 1, match = 0;
else u = ch1[c][u], match++;
val[i] = match;
}
u = 1;
for (i = 1; i <= m; ++i) u = nxt[t[i] - 'a'][u], rest[u] = val[i];
for (i = 0; i <= m; ++i) buc[i] = 0;
for (i = 1; i <= nid; ++i) buc[len[i]]++;
for (i = 1; i <= m; ++i) buc[i] += buc[i-1];
for (i = 1; i <= nid; ++i) a[buc[len[i]]--] = i;
for (i = nid; i >= 2; --i) rest[link[a[i]]] = max(rest[link[a[i]]], rest[a[i]]);
ll ans = 0;
for (i = 2; i <= nid; ++i) ans += max(0, min(len[i] - rest[i], len[i] - len[link[i]]));
printf("%lld\n", ans);
}
int main() {
scanf("%s", s+1);
n = strlen(s+1);
build();
scanf("%d", &q);
for (int i = 1; i <= q; ++i) {
scanf("%s%d%d", t+1, &L, &R);
calc();
}
return 0;
}