Description
小A 被选为了ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。
由于ION 已经举办了很多届，所以在题目命名上也是有规定的，ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。
由于一些特殊的原因，小A 不知道ION2017 每道题的名字，但是他通过一些特殊手段得到了ION2017 的命名串，现在小A 有Q 次询问：每次给定ION2017 的命名串和ION2018 的命名串，求有几种题目的命名，使得这个名字一定满足命题委员会的规定，即是ION2018 的命名串的一个非空连续子串且一定不会和ION2017 的任何一道题目的名字相同。
由于一些特殊原因，所有询问给出的ION2017 的命名串都是某个串的连续子串，详细可见输入格式。
Input
第一行一个字符串S ，之后询问给出的ION2017 的命名串都是S 的连续子串。 第二行一个正整数Q，表示询问次数。 接下来Q 行，每行有一个字符串T 和两个正整数l,r，表示询问如果ION2017 的 命名串是S [l..r]，ION2018 的命名串是T 的话，有几种命名方式一定满足规定。
Output
输出Q 行，第i 行一个非负整数表示第i 个询问的答案。
Sample Input
scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9
Sample Output
12
10
4
Solution
考虑\(l=1,r=|S|\)怎么做，先对\(S\)和\(T\)都建出后缀自动机，然后设\(lim_i\)表示字符串\(T\)的第\(i\)位能和\(S\)匹配到的最长的在\(T\)串以\(i\)为最后一个点的后缀是多少，也就是\(T[x...i]=S'\)，其中\(S'\)为\(S\)的任意一个子串，\(lim_i=\max\{i-x+1\}\)。
设\(pos[i]\)表示\(T\)的后缀自动机节点\(i\)的\(right\)集合最小的那个点。
那么如果能预处理这些东西，答案很显然就是：
\]
这个式子的意思也很显然，就是考虑\(T\)的\(SAM\)每个节点的贡献就好了。
考虑如何算\(lim_i\)，当前情况直接吧串\(T\)扔到\(S\)的后缀自动机上跑，然后失配了就跳\(parent\)就好了。
那么满分做法就很显然了，对于\(S\)的自动机上每个点开一个线段树来存\(right\)集合的分布情况，这个可以线段树合并搞搞，然后对于询问的\([l,r]\)区间，处理\(lim_i\)的时候，设当前的匹配长度是\(len\)，那么跳\(parent\)时判断一下有没有一个\(right\)集合的元素在区间\([l+len,r]\)之内，如果有就匹配上，没有就继续跳。
答案还是和上面一样算。
复杂度为\(O(|S|\log |S|+\sum|T|\log |S|)\)。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
#define ll long long
void print(ll x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(ll x) {if(!x) putchar('0');else print(x);putchar('\n');}
const int maxn = 1e6+10;
const int maxm = 2e7+10;
char s[maxn];
int rt[maxn],n,m;
// ======== Segment_Tree
#define mid ((l+r)>>1)
int SGT,ls[maxm],rs[maxm];
void modify(int &p,int l,int r,int x) {
if(!p) p=++SGT;
if(l==r) return ;
if(x<=mid) modify(ls[p],l,mid,x);
else modify(rs[p],mid+1,r,x);
}
int query(int p,int l,int r,int x,int y) {
if(!p||x>y) return 0;
if(x<=l&&r<=y) return 1;
if(x<=mid&&query(ls[p],l,mid,x,y)) return 1;
if(y>mid&&query(rs[p],mid+1,r,x,y)) return 1;
return 0;
}
int merge(int x,int y) {
if(!x||!y) return x+y;
int p=++SGT;
ls[p]=merge(ls[x],ls[y]);
rs[p]=merge(rs[x],rs[y]);
return p;
}
// ========
namespace sam { // string S 's Suffix Automaton
int cnt=1,qs=1,lstp=1;
int tr[maxn][27],par[maxn],ml[maxn],vis[maxn],t[maxn],r[maxn];
void append(int x) {
int p=lstp,np=++cnt;ml[np]=ml[p]+1,vis[np]=1;lstp=np;
for(;p&&tr[p][x]==0;p=par[p]) tr[p][x]=np;
if(!p) return par[np]=qs,void();
int q=tr[p][x];
if(ml[p]+1<ml[q]) {
int nq=++cnt;ml[nq]=ml[p]+1;
memcpy(tr[nq],tr[q],sizeof tr[nq]);
par[nq]=par[q],par[q]=par[np]=nq;
for(;p&&tr[p][x]==q;p=par[p]) tr[p][x]=nq;
} else par[np]=q;
}
void prepare() {
scanf("%s",s+1);n=strlen(s+1);
for(int i=1;i<=n;i++) append(s[i]-'a'+1);
for(int i=1;i<=cnt;i++) t[ml[i]]++;
for(int i=1;i<=n;i++) t[i]+=t[i-1];
for(int i=1;i<=cnt;i++) r[t[ml[i]]--]=i; //toposort
for(int i=cnt;i;i--) {
if(vis[r[i]]) modify(rt[r[i]],1,n,ml[r[i]]);
if(par[r[i]]) rt[par[r[i]]]=merge(rt[par[r[i]]],rt[r[i]]);
}
}
}
namespace sam2 { //string T 's Suffix Automaton
int cnt,qs=1,lstp;
int tr[maxn][27],ml[maxn],pos[maxn],par[maxn],lim[maxn];
void init() {cnt=lstp=1;memset(tr[1],0,sizeof tr[1]);}
int newnode(int x) {ml[++cnt]=x;memset(tr[cnt],0,sizeof tr[cnt]),par[cnt]=0;return cnt;}
void append(int x) {
int p=lstp,np=newnode(ml[p]+1);pos[np]=ml[np];lstp=np;
for(;p&&tr[p][x]==0;p=par[p]) tr[p][x]=np;
if(!p) return par[np]=qs,void();
int q=tr[p][x];
if(ml[p]+1<ml[q]) {
int nq=newnode(ml[p]+1);pos[nq]=pos[q];
memcpy(tr[nq],tr[q],sizeof tr[nq]);
par[nq]=par[q],par[q]=par[np]=nq;
for(;p&&tr[p][x]==q;p=par[p]) tr[p][x]=nq;
} else par[np]=q;
}
ll solve() {
init();int L,R;
scanf("%s",s+1);m=strlen(s+1);read(L),read(R);
int now=qs,len=0;
for(int i=1;i<=m;i++) {
int x=s[i]-'a'+1;
append(x);
while(1) { // run on automaton 1
if(sam :: tr[now][x]&&query(rt[sam ::tr[now][x]],1,n,L+len,R)) {
now=sam :: tr[now][x],len++;break;
}
if(!len) break;len--;
if(len==sam :: ml[sam :: par[now]]) now=sam :: par[now];
}lim[i]=len;
}
ll ans=0;
for(int i=2;i<=cnt;i++) ans+=max(0,ml[i]-max(lim[pos[i]],ml[par[i]]));
return ans;
}
}
int main() {
sam :: prepare();
int T;read(T);while(T--) write(sam2 :: solve());
return 0;
}