代码有点长就不放在这里力，可以点提交记录看
by 永无岛 @ 2020-06-13 19:53:02
看不到
by UnyieldingTrilobite @ 2020-06-13 20:08:06
```cpp
#include<bits/stdc++.h>
using namespace std;
const int len_T=500005,len_S=1000005;
char T[len_T],S[len_S];
int ls[len_T*80],rs[len_T*80],n,m,t,tot1=1,tot2=1,las1=1,las2=1,cnt,p,len,L,R;
int b[len_T],sa[2*len_T],lcs[len_S];
long long ans;
struct SAM_point {
int ch[26];
int len,fa,pre,root;
} SAM_T[2*len_T],SAM_S[2*len_S];
void insert(int &root,int l,int r,int pos) {
if(!root)root=++cnt;
if(l==r)return;
int mid((l+r)>>1);
if(mid>=pos)insert(ls[root],l,mid,pos);
else insert(rs[root],mid+1,r,pos);
}
int merge(int x,int y) {
if(!x||!y)return x|y;
int now=++cnt;
ls[now]=merge(ls[x],ls[y]);
rs[now]=merge(rs[x],rs[y]);
return now;
}
int query(int l,int r,int now,int ql,int qr) {
if(!now)return 0;
if(l>=ql&&r<=qr)return 1;
int mid((l+r)>>1);
if(ql<=mid&&query(l,mid,ls[now],ql,qr))return 1;
if(qr>mid&&query(mid+1,r,rs[now],ql,qr))return 1;
return 0;
}
void insert1(int c,int pr) {
int p=las1,np=las1=++tot1;
SAM_T[np].len=SAM_T[p].len+1;
SAM_T[np].pre=pr;
for(; p&&!SAM_T[p].ch[c]; p=SAM_T[p].fa)SAM_T[p].ch[c]=np;
if(!p) {
SAM_T[np].fa=1;
return;
} else {
int q=SAM_T[p].ch[c];
if(SAM_T[q].len==SAM_T[p].len+1) {
SAM_T[np].fa=q;
return;
} else {
int nq=++tot1;
SAM_T[nq]=SAM_T[q];
SAM_T[nq].pre=0;
SAM_T[nq].len=SAM_T[p].len+1;
SAM_T[np].fa=SAM_T[q].fa=nq;
for(; p&&SAM_T[p].ch[c]==q; p=SAM_T[p].fa)SAM_T[p].ch[c]=nq;
}
}
return;
}
void insert2(int c,int pr) {
int p=las2,np=las2=++tot2;
SAM_S[np].len=SAM_S[p].len+1;
SAM_S[np].pre=pr;
for(; p&&!SAM_S[p].ch[c]; p=SAM_S[p].fa)SAM_S[p].ch[c]=np;
if(!p) {
SAM_S[np].fa=1;
} else {
int q=SAM_S[p].ch[c];
if(SAM_S[q].len==SAM_S[p].len+1) {
SAM_S[np].fa=q;
} else {
int nq=++tot2;
SAM_S[nq]=SAM_S[q];
SAM_S[nq].len=SAM_S[p].len+1;
SAM_S[np].fa=SAM_S[q].fa=nq;
for(; p&&SAM_S[p].ch[c]==q; p=SAM_S[p].fa)SAM_S[p].ch[c]=nq;
}
}
return;
}
void build_SAM_T() {
for(int i=1; i<=n; i++)
insert1(T[i]-'a',i);
for(int i=1; i<=tot1; i++) ++b[SAM_T[i].len];
for(int i=1; i<=n; i++)b[i]+=b[i-1];
for(int i=tot1; i>1; i--)
sa[b[SAM_T[i].len]--]=i;
for(int i=tot1; i>1; i--) {
if(SAM_T[sa[i]].pre)
insert(SAM_T[sa[i]].root,1,n,SAM_T[sa[i]].pre);
SAM_T[SAM_T[sa[i]].fa].root=merge(SAM_T[SAM_T[sa[i]].fa].root,SAM_T[sa[i]].root);
}
return;
}
void clear1() {
for(int i=1; i<=2*len_T; i++) {
for(int j=0; j<26; j++)
SAM_T[i].ch[j]=0;
SAM_T[i].fa=SAM_T[i].len=SAM_T[i].pre=SAM_T[i].root=0;
}
return;
}
void clear2() {
for(int i=1; i<=tot2; i++) {
for(int j=0; j<26; j++)
SAM_S[i].ch[j]=0;
SAM_S[i].fa=SAM_S[i].len=SAM_S[i].pre=SAM_S[i].root=0;
}
las2=tot2=1;
m=strlen(S+1);
p=1;
len=ans=0;
return;
}
int main() {
clear1();
scanf("%s",T+1);
n=strlen(T+1);
build_SAM_T();
cin>>t;
while(t--) {
scanf("%s",S+1);
scanf("%d%d",&L,&R);
clear2();
for(int i=1; i<=m; i++) {
insert2(S[i]-'a',i);
while(1) {
if(SAM_T[p].ch[(int) S[i]-'a']&&query(1,n,SAM_T[SAM_T[p].ch[(int) S[i]-'a']].root,L+len,R)) {
p=SAM_T[p].ch[(int) S[i]-'a'];
++len;
break;
}
if(!len)break;
else {
p=SAM_T[p].fa;
len=SAM_T[p].len;
}
}
lcs[i]=len;
}
for(int i=2; i<=tot2; i++) {
ans+=(long long)max(0,SAM_S[i].len-max(SAM_S[SAM_S[i].fa].len,lcs[SAM_S[i].pre]));
}
printf("%lld\n",ans);
}
return 0;
}
/*
scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9
*/
```
码风可能不太好请见谅
by 永无岛 @ 2020-06-13 20:10:09
我甚至不会...我还有很长的路要走
by marve197 @ 2022-05-07 22:41:08