简明题意:你有一个字符串(S),每次询问一个字符串(T)和区间([l,r]),求(T)中不在(S[l,r])中出现的本质不同的子串个数
不在(S[l,r])中出现可以转化成(T)的所有子串减去在(S[l,r])中出现
首先考虑(l=1,r=|S|)时的做法
我们对于(T)的每一个前缀([1,i])计算出最长的是(S)的子串的后缀长度
这个很好求,先对(S)做后缀自动机，假设我们已经匹配到了(T)串的第i个字符,当前最长匹配长度为l,如果(S)的parent树上有出边为(T_i),那么就走到这个点,并且l++;否则就往上跳直到有(T_i)这条出边为止,然后l变为这个点的len然后再继续匹配就可以;跳到根还没有出边的话当前l就为0
然后要求(T)的在(S[l,r])出现的本质不同的子串个数
既然我们已经得到了上面的那个东西,那么只要计算出(T)的每个节点出现的本质不同的子串个数就可以了,这个直接对(T)做后缀自动机,然后([max(len_{fa_x},l),len_x])都可以算作答案
那么推广到这个题上来
思考上面在(S)的parent树上跳的那个过程,现在的是区间([l,r]),那么可能(fa_x)不在([l,r])里,也就是比l小,这样我们是不能转移的,所以我们考虑这个点的endpos的集合,我们应该找到一个位置p使得(p-len_x+1geq l),那么为了便于维护,我们要找到一个最大的(p-len_x+1),那也就是p最大
于是这就是一个二维偏序,第一维是(pleq l),第二维是p要在x的子树中
第一维直接对询问离线,然后对右端点排序,往右加点就可以
第二维考虑对parent树dfs,然后这就是一个区间问题了
有一点要注意的是,当(p-len_x+1le l)时,x的父亲可能会有左端点比l大,但是长度越过了l,跳点的时候还要加上这种情况
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define zrt k << 1
#define yrt k << 1 | 1
const int N = 5e5;
using namespace std;
int n,m,T,nxt[N * 2 + 5],head[N * 2 + 5],edge[N * 2 + 5],edge_cnt;
int size[N * 2 + 5],dfn_cnt,dfn[N * 2 + 5],f[N * 2 + 5];
long long ans[N + 5];
char s[N + 5],t[N * 2 + 5];
struct Q
{
int l,r,st,ed,id;
}q[N + 5];
struct sam
{
int fa[N * 2 + 5],len[N * 2 + 5],cnt,las,ch[N * 2 + 5][26],ep[N * 2 + 5],mp[N * 2 + 5];
sam()
{
cnt = las = 1;
}
void clear()
{
for (int i = 1;i <= cnt;i++)
{
ep[i] = mp[i] = len[i] = fa[i] = 0;
for (int j = 0;j < 26;j++)
ch[i][j] = 0;
}
cnt = las = 1;
}
void insert(int c,int id)
{
int q = ++cnt,p = las;
las = q;
len[q] = len[p] + 1;
ep[q] = id;
mp[id] = q;
while (p && ! ch[p][c])
{
ch[p][c] = q;
p = fa[p];
}
if (!p)
fa[q] = 1;
else
{
int x = ch[p][c];
if (len[x] == len[p] + 1)
fa[q] = x;
else
{
int y = ++cnt;
ep[y] = id;
len[y] = len[p] + 1;
fa[y] = fa[x];
fa[x] = fa[q] = y;
for (int i = 0;i < 26;i++)
ch[y][i] = ch[x][i];
while (p && ch[p][c] == x)
{
ch[p][c] = y;
p = fa[p];
}
}
}
}
}a,b;
int cmp(Q x,Q y)
{
return x.r < y.r;
}
void add_edge(int u,int v)
{
edge[++edge_cnt] = v;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void dfs(int u)
{
dfn[u] = ++dfn_cnt;
size[u] = 1;
for (int i = head[u];i;i = nxt[i])
{
int v = edge[i];
dfs(v);
size[u] += size[v];
}
}
struct Seg
{
int mx[N * 8 + 5];
void upd(int k)
{
mx[k] = max(mx[zrt],mx[yrt]);
}
void modify(int k,int l,int r,int x,int z)
{
if (l == r)
{
mx[k] = z;
return;
}
int mid = l + r >> 1;
if (x <= mid)
modify(zrt,l,mid,x,z);
else
modify(yrt,mid + 1,r,x,z);
upd(k);
}
int query(int k,int l,int r,int x,int y)
{
if (l >= x && r <= y)
return mx[k];
int mid = l + r >> 1;
if (x > mid)
return query(yrt,mid + 1,r,x,y);
else
if (y <= mid)
return query(zrt,l,mid,x,y);
else
return max(query(zrt,l,mid,x,y),query(yrt,mid + 1,r,x,y));
}
}tree;
int main()
{
scanf("%s",s + 1);
n = strlen(s + 1);
for (int i = 1;i <= n;i++)
a.insert(s[i] - 'a',i);
for (int i = 2;i <= a.cnt;i++)
add_edge(a.fa[i],i);
dfs(1);
scanf("%d",&T);
int l,r;
m = 1;
for (int i = 1;i <= T;i++)
{
scanf("%s",t + m);
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id = i;
q[i].st = m;
m += strlen(t + m);
q[i].ed = m - 1;
}
sort(q + 1,q + T + 1,cmp);
for (int i = 1,j = 1;i <= T;i++)
{
while (j <= q[i].r)
{
tree.modify(1,1,dfn_cnt,dfn[a.mp[j]],j);
j++;
}
for (int k = q[i].st;k <= q[i].ed;k++)
b.insert(t[k] - 'a',k - q[i].st + 1);
int u = 1,ll = 0;
for (int k = q[i].st;k <= q[i].ed;k++)
{
int v = a.ch[u][t[k] - 'a'];
if (v)
u = v,ll++;
else
{
u = a.fa[u];
while (u)
{
if (a.ch[u][t[k] - 'a'])
{
ll = a.len[u] + 1;
u = a.ch[u][t[k] - 'a'];
break;
}
u = a.fa[u];
}
if (!u)
u = 1,ll = 0;
}
while (u)
{
int mx = tree.query(1,1,dfn_cnt,dfn[u],dfn[u] + size[u] - 1);
if (mx && mx - ll + 1 >= q[i].l)
break;
if (mx && mx - a.len[a.fa[u]] + 1 > q[i].l)
{
ll = mx - q[i].l + 1;
break;
}
u = a.fa[u];
ll = a.len[u];
}
f[k - q[i].st + 1] = ll;
}
for (int k = 2;k <= b.cnt;k++)
ans[q[i].id] += max(b.len[k] - max(f[b.ep[k]],b.len[b.fa[k]]),0);
b.clear();
}
for (int i = 1;i <= T;i++)
printf("%lld
",ans[i]);
return 0;
}