题目描述
小 A 被选为了 ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。
由于 ION 已经举办了很多届，所以在题目命名上也是有规定的，ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。
由于一些特殊的原因，小 A 不知道 ION2017 每道题的名字，但是他通过一些特殊手段得到了 ION2017 的命名串，现在小 A 有 \(Q\) 次询问：每次给定 ION2017 的命名串和 ION2018 的命名串，求有几种题目的命名，使得这个名字一定满足命题委员会的规定，即是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。
由于一些特殊原因，所有询问给出的 ION2017 的命名串都是某个串的连续子串，详细可见输入格式。
输入格式
第一行一个字符串 \(S\) ，之后询问给出的 ION2017 的命名串都是 \(S\) 的连续子串。
第二行一个正整数 \(Q\)，表示询问次数。
接下来 \(Q\) 行，每行有一个字符串 \(T\) 和两个正整数\(l,r\)，表示询问如果 ION2017 的命名串是 \(S_{l\ldots r}\)，ION2018 的命名串是 \(T\) 的话，有几种命名方式一定满足规定。
对于所有数据，保证 \(1\leq l \leq r \leq |S|\),\(1\leq |T|,|S|\leq 5 \times 10^5,1\le q\le 10^5,\sum|T|\le 10^6\)
考虑全局询问怎么做，正难则反，考虑有多少个 \(S\) 和 \(T\) 的本质不同公共串。
考虑双指针，枚举 \(T\)的右端点，双指针维护左端点，在后缀自动机上的表现就是不断跳 fail 树上的父亲直到在 DAG 上有出边。这样子得到了 \(O(|T|)\) 个极大区间，那么在 \(T\) 的 fail 树上所有区间对应节点的父亲都是符合要求的。在上面搜一遍得到答案就可以了。
那么区间询问呢？可持久化线段树合并维护 endpos 集合，在维护双指针的时候判断一下到达的点在不在区间内就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long LL;
int x[N],y[N],p[N],m,n,q,len[N],cnt;
char str[N],t[N];
struct SAM{
int tr[N*20],lc[N*20],rc[N*20],l[N],ch[N][26],fa[22][N],tme,idx=1,hd[N],ls=1,dfn[N],cnt,rt[N],dep[N],e_num,gl,gr;
struct edge{
int v,nxt;
}e[N];
void add_edge(int u,int v)
{
e[++e_num]=(edge){v,hd[u]};
hd[u]=e_num;
}
void upd(int&o,int l,int r,int x)
{
if(!o)
o=++tme;
if(l==r)
return tr[o]=l,void();
int md=l+r>>1;
if(md>=x)
upd(lc[o],l,md,x);
else
upd(rc[o],md+1,r,x);
tr[o]=max(tr[lc[o]],tr[rc[o]]);
}
int ask(int o,int l,int r,int y)
{
if(!o)
return 0;
if(r<=y)
return tr[o];
int md=l+r>>1,ret=0;
if(md<y)
ret=ask(rc[o],md+1,r,y);
if(!ret)
ret=ask(lc[o],l,md,y);
return ret;
}
int merge(int x,int y)
{
if(!x||!y)
return x|y;
int p=++tme;
lc[p]=merge(lc[x],lc[y]);
rc[p]=merge(rc[x],rc[y]);
tr[p]=max(tr[x],tr[y]);
return p;
}
void dfs(int x)
{
dfn[x]=++cnt,dep[x]=dep[fa[0][x]]+1;
for(int i=hd[x];i;i=e[i].nxt)
dfs(e[i].v),rt[x]=merge(rt[x],rt[e[i].v]);
}
void init()
{
l[0]=-1;
for(int i=1;i<=20;i++)
for(int j=1;j<=idx;j++)
fa[i][j]=fa[i-1][fa[i-1][j]];
for(int i=1;i<=idx;i++)
add_edge(fa[0][i],i);
dfs(1);
}
void insert(int c)
{
int k=ls,p=++idx;
l[p]=l[ls]+1;
ls=p;
upd(rt[p],1,n,l[p]);
while(k&&!ch[k][c])
ch[k][c]=p,k=fa[0][k];
if(!k)
fa[0][p]=1;
else
{
int q=ch[k][c];
if(l[k]==l[q]+1)
fa[0][p]=q;
else
{
int nw=++idx;
l[nw]=l[k]+1,fa[0][nw]=fa[0][q];
memcpy(ch[nw],ch[q],sizeof(ch[0]));
fa[0][q]=fa[0][p]=nw;
while(ch[k][c]==q)
ch[k][c]=nw,k=fa[0][k];
}
}
}
void put(int o,int l,int r)
{
if(!o)
return;
if(l==r)
printf("%d ",l);
int md=l+r>>1;
put(lc[o],l,md);
put(rc[o],md+1,r);
}
void solve(int pl,int r)
{
int nw=1,gl=1,k=0;
LL ans=0;
for(int i=1;i<=m;i++)
{
while(nw)
{
int to=ch[nw][t[i]-'a'];
if(to&&ask(rt[to],1,n,r)>=pl+l[fa[0][to]])
break;
nw=fa[0][nw];
}
int le=min(len[i-1]+1,l[nw]+1);
nw=ch[nw][t[i]-'a']? ch[nw][t[i]-'a']:1;
len[i]=min(le,ask(rt[nw],1,n,r)-pl+1);
}
}
}s;
int l[N],ch[N][26],fa[22][N],ls=1,idx=1,rr[N],hd[N],tg[N],e_num;
struct edge{
int v,nxt;
}e[N];
void add_edge(int u,int v)
{
e[++e_num]=(edge){v,hd[u]};
hd[u]=e_num;
}
LL dfs(int x)
{
LL ret=0;
for(int i=hd[x];i;i=e[i].nxt)
{
ret+=dfs(e[i].v);
if(tg[e[i].v])
{
tg[x]=l[x];
ret+=tg[e[i].v]-l[x];
}
}
return ret;
}
LL ask(int pl,int r)
{
s.solve(pl,r);
e_num=hd[1]=tg[1]=0;
memset(ch[1],0,sizeof(ch[1]));
ls=idx=1;
for(int i=1;i<=m;i++)
{
int c=t[i]-'a',k=ls,p=++idx;
memset(ch[p],0,sizeof(ch[p]));
l[p]=l[k]+1,ls=p;
tg[rr[i]=p]=hd[p]=0;
while(k&&!ch[k][c])
ch[k][c]=p,k=fa[0][k];
if(!k)
fa[0][p]=1;
else
{
int q=ch[k][c];
if(l[q]==l[k]+1)
fa[0][p]=q;
else
{
int nw=++idx;
memcpy(ch[nw],ch[q],sizeof(ch[0]));
tg[nw]=hd[nw]=0;
fa[0][nw]=fa[0][q],l[nw]=l[k]+1;
fa[0][p]=fa[0][q]=nw;
while(ch[k][c]==q)
ch[k][c]=nw,k=fa[0][k];
}
}
}
LL ans=0;
for(int i=2;i<=idx;i++)
ans+=l[i]-l[fa[0][i]],add_edge(fa[0][i],i);
for(int i=1;i<=20;i++)
for(int j=1;j<=idx;j++)
fa[i][j]=fa[i-1][fa[i-1][j]];
for(int i=1;i<=m;i++)
{
int k=rr[i];
for(int j=20;~j;--j)
if(fa[j][k]&&l[fa[j][k]]>=len[i])
k=fa[j][k];
tg[k]=len[i];
}
return ans-dfs(1);
}
int main()
{
scanf("%s",str+1);
n=strlen(str+1);
for(int i=1;i<=n;i++)
s.insert(str[i]-'a');
s.init();
scanf("%d",&q);
while(q--)
{
int l,r;
scanf("%s%d%d",t+1,&l,&r);
m=strlen(t+1);
printf("%lld\n",ask(l,r));
}
}