题目描述
小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*50],ls[N*50],rs[N*50],T[N],n,tong[N],rnk[N],liml,limr; char s[N]; inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);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)>>1; if(mid>=x)upd(ls[cnt],l,mid,x); else upd(rs[cnt],mid+1,r,x); } int merge(int now,int pre,int l,int r){ if(!now||!pre)return now^pre; int mid=(l+r)>>1,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+1,r); return p; } int query(int cnt,int l,int r,int L,int R){ if(L>R)return 0; if(l>=L&&r<=R)return tr[cnt]; int mid=(l+r)>>1,ans=0; if(mid>=L)ans=max(ans,query(ls[cnt],l,mid,L,R)); if(mid<R)ans=max(ans,query(rs[cnt],mid+1,r,L,R)); return ans; } struct SAM1{ int ch[N][26],l[N],fa[N],cnt,last; SAM1(){cnt=last=1;} inline void ins(int x,int id){ int p=last,np=++cnt;l[np]=l[p]+1;last=np;//cout<<cnt; upd(T[np],1,n,id); for(;p&&!ch[p][x];p=fa[p])ch[p][x]=np; if(!p)fa[np]=1; else{ int q=ch[p][x]; if(l[p]+1==l[q])fa[np]=q; else{ int nq=++cnt;l[nq]=l[p]+1; 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=1;i<=cnt;++i)tong[l[i]]++; for(int i=1;i<=n;++i)tong[i]+=tong[i-1]; for(int i=cnt;i>=1;--i)rnk[tong[l[i]]--]=i; for(int i=cnt;i>=1;--i){ int x=rnk[i]; if(fa[x])T[fa[x]]=merge(T[fa[x]],T[x],1,n); //check(T[x],1,n);//cout<<x<<endl; } } }S; struct SAM2{ int ch[N<<1][26],l[N<<1],fa[N<<1],cnt,last,pp[N<<1]; bool tag[N<<1]; SAM2(){cnt=last=1;} inline void ins(int x){ int p=last,np=++cnt;l[np]=l[p]+1;last=np; for(;p&&!ch[p][x];p=fa[p])ch[p][x]=np; if(!p)fa[np]=1; else{ int q=ch[p][x]; if(l[p]+1==l[q])fa[np]=q; else{ int nq=++cnt;l[nq]=l[p]+1; 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=0; for(int i=2;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]]+1>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]=1,pp[x]=l[x]; } inline ll work(int nn){ for(int i=1;i<=nn;++i)ins(s[i]-'a'); int now=1,now2=1,len=0; for(int i=1;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']],1,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']],1,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<0){now=0;len=0;break;} } if(now)len++,now=S.ch[now][s[i]-'a']; else now=1,len=0; } if(len){ int x=query(T[now],1,n,liml,limr);x=min(max(0,x-liml+1),len); get_work(now2,x); } } return calc(n); } inline void clear(){ for(int i=0;i<=cnt;++i){ fa[i]=tag[i]=pp[i]=l[i]=0; for(int j=0;j<26;++j)ch[i][j]=0; } cnt=last=1; } }t; int main(){ scanf("%s",s+1);int q=rd();n=strlen(s+1); for(int i=1;i<=n;++i)S.ins(s[i]-'a',i); S.prework(); while(q--){ scanf("%s",s+1);int len=strlen(s+1);liml=rd();limr=rd(); printf("%lld ",t.work(len)); t.clear(); } return 0; }