题目描述
小A 被选为了ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。
由于ION 已经举办了很多届，所以在题目命名上也是有规定的，ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。
由于一些特殊的原因，小A 不知道ION2017 每道题的名字，但是他通过一些特殊手段得到了ION2017 的命名串，现在小A 有Q 次询问：每次给定ION2017 的命名串和ION2018 的命名串，求有几种题目的命名，使得这个名字一定满足命题委员会的规定，即是ION2018 的命名串的一个非空连续子串且一定不会和ION2017 的任何一道题目的名字相同。
由于一些特殊原因，所有询问给出的ION2017 的命名串都是某个串的连续子串，详细可见输入格式。
题解
题目大意：给定一个S串，每次询问一个T串，和l-r询问有多少字符串在T串出现过，且在S串的l-r中没有出现过。
这道题有一个部分分，所有询问的l=1,r=s。
也就是说问有多少字符串在T串中出现过，在S串中没有出现过。
或者说如果我们对T串建SAM，那么答案就是∑l[i]-max(l[fa[i]],p[i]),p[i]是当前节点的串和S串的最长后缀的长度。
我们的任务就是求p[i]。
我们可以对S建SAM，然后S串和T串一块跑，我们求可以求出T串的每一个后缀和S串的最长公共后缀的长度。
假设现在我们匹配到了now节点，匹配长度为len，然后我们就去跳now的fail树，找到第一个合法的节点更新匹配长度。
然后这个节点的所有祖先会全部完全匹配。
这时为了保证复杂度，我们给完全匹配的节点打上标记，这样就可以保证总复杂度为O(n)了。
于是我们就拿到了68分。
下面考虑l和r任意的情况。
这时我们要注意一个问题，就是我们在找下一个节点转移的时候，不能只看有没有转移边了，因为有转移边不一定意味着在l到r里出现过。
所以我们在判断的时候加上一句，假设当前匹配长度为len，我们需要判断在S串l+len~r中有没有出现一个后缀节点，如果没有，就失配。
这个东西用线段树维护right集合来实现，注意每次合并都要新建一条链，否则会导致原来的信息被修改。
然后我们交上去，发现WA了一个点，这是为什么呢？
因为我们做一般的匹配的时候，如果失配就直接跳father，但这个时候对于长度为len的失配了，对于长度为len-1的有可能会成功，所以每次失配应当让len–，当len变成当前节点的父亲节点的len是再去跳father。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1000009
#define M 30
using namespace std;
typedef long long ll;
int top,tr[N*],ls[N*],rs[N*],T[N],n,tong[N],rnk[N],liml,limr;
char s[N];
inline ll rd(){
ll x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
void upd(int &cnt,int l,int r,int x){
cnt=++top;tr[cnt]=x;
if(l==r)return;
int mid=(l+r)>>;
if(mid>=x)upd(ls[cnt],l,mid,x);
else upd(rs[cnt],mid+,r,x);
}
int merge(int now,int pre,int l,int r){
if(!now||!pre)return now^pre;
int mid=(l+r)>>,p=++top;//cout<<top<<" ";
tr[p]=max(tr[now],tr[pre]);
if(l==r)return p;
ls[p]=merge(ls[now],ls[pre],l,mid);rs[p]=merge(rs[now],rs[pre],mid+,r);
return p;
}
int query(int cnt,int l,int r,int L,int R){
if(L>R)return ;
if(l>=L&&r<=R)return tr[cnt];
int mid=(l+r)>>,ans=;
if(mid>=L)ans=max(ans,query(ls[cnt],l,mid,L,R));
if(mid<R)ans=max(ans,query(rs[cnt],mid+,r,L,R));
return ans;
}
struct SAM1{
int ch[N][],l[N],fa[N],cnt,last;
SAM1(){cnt=last=;}
inline void ins(int x,int id){
int p=last,np=++cnt;l[np]=l[p]+;last=np;//cout<<cnt;
upd(T[np],,n,id);
for(;p&&!ch[p][x];p=fa[p])ch[p][x]=np;
if(!p)fa[np]=;
else{
int q=ch[p][x];
if(l[p]+==l[q])fa[np]=q;
else{
int nq=++cnt;l[nq]=l[p]+;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;ch[p][x]==q;p=fa[p])ch[p][x]=nq;
}
}
}
inline void prework(){
for(int i=;i<=cnt;++i)tong[l[i]]++;
for(int i=;i<=n;++i)tong[i]+=tong[i-];
for(int i=cnt;i>=;--i)rnk[tong[l[i]]--]=i;
for(int i=cnt;i>=;--i){
int x=rnk[i];
if(fa[x])T[fa[x]]=merge(T[fa[x]],T[x],,n);
//check(T[x],1,n);//cout<<x<<endl;
}
}
}S;
struct SAM2{
int ch[N<<][],l[N<<],fa[N<<],cnt,last,pp[N<<];
bool tag[N<<];
SAM2(){cnt=last=;}
inline void ins(int x){
int p=last,np=++cnt;l[np]=l[p]+;last=np;
for(;p&&!ch[p][x];p=fa[p])ch[p][x]=np;
if(!p)fa[np]=;
else{
int q=ch[p][x];
if(l[p]+==l[q])fa[np]=q;
else{
int nq=++cnt;l[nq]=l[p]+;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;ch[p][x]==q;p=fa[p])ch[p][x]=nq;
}
}
}
ll calc(int len){
ll ans=;
for(int i=;i<=cnt;++i)ans+=l[i]-max(pp[i],l[fa[i]]);
return ans;
}
inline void get_work(int x,int len){
for(;x&&l[fa[x]]+>len&&!tag[x];x=fa[x]);
// cout<<tag[x];
pp[x]=max(pp[x],len);
x=fa[x];
for(;x&&!tag[x];x=fa[x])tag[x]=,pp[x]=l[x];
}
inline ll work(int nn){
for(int i=;i<=nn;++i)ins(s[i]-'a');
int now=,now2=,len=;
for(int i=;i<=nn;++i){
// cout<<i<<" ";
now2=ch[now2][s[i]-'a'];
if(S.ch[now][s[i]-'a']&&query(T[S.ch[now][s[i]-'a']],,n,liml+len,limr))len++,now=S.ch[now][s[i]-'a'];else{
while(now&&(!S.ch[now][s[i]-'a']||!query(T[S.ch[now][s[i]-'a']],,n,liml+len,limr))){
// now=S.fa[now],len=S.l[now];
len--;if(len==S.l[S.fa[now]])now=S.fa[now];
if(len<){now=;len=;break;}
}
if(now)len++,now=S.ch[now][s[i]-'a'];
else now=,len=;
}
if(len){
int x=query(T[now],,n,liml,limr);x=min(max(,x-liml+),len);
get_work(now2,x);
}
}
return calc(n);
}
inline void clear(){
for(int i=;i<=cnt;++i){
fa[i]=tag[i]=pp[i]=l[i]=;
for(int j=;j<;++j)ch[i][j]=;
}
cnt=last=;
}
}t;
int main(){
scanf("%s",s+);int q=rd();n=strlen(s+);
for(int i=;i<=n;++i)S.ins(s[i]-'a',i);
S.prework();
while(q--){
scanf("%s",s+);int len=strlen(s+);liml=rd();limr=rd();
printf("%lld\n",t.work(len));
t.clear();
}
return ;
}
