抄题解的时候其实感觉都还挺套路的。
然而我还是抄了三天
。
造$SAM$，线段树合并得到$endpos$集合。倍增定位到$[l,r]$代表的节点，对于某一个长度$L$，有$endpos\in [l+L,r]$的节点在$[l,r]$出现过。$T$的子串都是前缀的后缀，找一下$T$每个前缀最长的在$[l,r]$出现过的后缀，记它的长度为$L$。
到这儿都比较套路了。
一开始想倍增找，然而是$\log^2$的，而且并不能确定$L$也无法保证跳到的节点是否正确。
出门右转题解区，其实直接暴力跳就好。不断缩减$L$检验是否满足条件，若$L$不满足当前节点就跳$fa$。复杂度$O(|T|\log)$。
然后是去重的问题。
$SAM$本身就能解决本质不同的子串数量，对$T$造$SAM$，不考虑$L$就有$\sum len[i]-len[fa[i]]$。考虑上就给每个节点限制一个$ma$，表示该节点的串最小长度为$ma$，前面求的$L$求的是每个前缀的限制，就把$L$限制在含有前缀的节点上，复制点也要把$ma$复制过去。答案就为$\sum \max\{len[i]-\max(len[fa[i]],ma[i]),0\}$（可能有负数对$0$取$\max$）
代码：
//以下所有比普通SAM多了个t的都是T的SAM
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 1000005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
#define ls(x) ls[x]
#define rs(x) rs[x]
#define son(x,y) son[x][y]
#define sont(x,y) sont[x][y]
int ls[maxn*25],rs[maxn*25],h[maxn],num,all,n;
int son[maxn][26],fa[maxn],len[maxn],root[maxn],w[maxn]={1},last=1,cnt=1;
int sont[maxn][26],fat[maxn],lent[maxn],ma[maxn],lastt,cntt;
char s[maxn];
struct edge{
int pre,to;
}e[maxn];
inline void add(int from,int to){
e[++num].pre=h[from],h[from]=num,e[num].to=to;
}
void modify(int poi,int l,int r,int &node){
node=++all;
if(l==r)return;
int mid=l+r>>1;
if(poi<=mid)modify(poi,l,mid,ls(node));
else modify(poi,mid+1,r,rs(node));
}
int ask(int L,int R,int l,int r,int node){
if(!node)return 0;
if(L<=l&&R>=r)return 1;
int mid=l+r>>1;
if(L<=mid&&ask(L,R,l,mid,ls(node)))return 1;
if(R>mid&&ask(L,R,mid+1,r,rs(node)))return 1;
return 0;
}
int merge(int x,int y){
if(!x||!y)return x|y;
int ne=++all;
ls(ne)=merge(ls(x),ls(y));
rs(ne)=merge(rs(x),rs(y));
return ne;
}
void insert(int c){
int p=last,ne=last=++cnt;
modify(len[ne]=len[p]+1,1,n,root[ne]);
while(p&&!son(p,c))son(p,c)=ne,p=fa[p];
if(!p)fa[ne]=1;
else {
int q=son(p,c);
if(len[q]==len[p]+1)fa[ne]=q;
else {
int sp=++cnt;
memcpy(son[sp],son[q],sizeof son[q]);
len[sp]=len[p]+1,fa[sp]=fa[q],fa[q]=fa[ne]=sp;
while(p&&son(p,c)==q)son(p,c)=sp,p=fa[p];
}
}
}
void dfs(int node=1){
int x;
for(register int i=h[node];i;i=e[i].pre)
x=e[i].to,dfs(x),root[node]=merge(root[node],root[x]);
}
inline void init(){
memset(sont[1],0,sizeof sont[1]);
lastt=1,cntt=1;
}
long long calc(){
long long ans=0;
for(register int i=2;i<=cntt;++i)
ans+=max(0,lent[i]-max(lent[fat[i]],ma[i]));
return ans;
}
void insertt(int c,int d){
int p=lastt,ne=lastt=++cntt;
memset(sont[ne],0,sizeof sont[ne]);
lent[ne]=lent[p]+1,ma[ne]=d;
while(p&&!sont(p,c))sont(p,c)=ne,p=fat[p];
if(!p)fat[ne]=1;
else {
int q=sont(p,c);
if(lent[q]==lent[p]+1)fat[ne]=q;
else {
int sp=++cntt;
memcpy(sont[sp],sont[q],sizeof sont[q]);
ma[sp]=ma[q],lent[sp]=lent[p]+1,fat[sp]=fat[q],fat[q]=fat[ne]=sp;
while(p&&sont(p,c)==q)sont(p,c)=sp,p=fat[p];
}
}
}
int main(){
scanf("%s",s+1),n=strlen(s+1);
int m,l,r,node,N,L;
for(register int i=1;i<=n;++i)insert(s[i]-'a');
for(register int i=1;i<=n;++i)w[i]=son(w[i-1],s[i]-'a');
for(register int i=2;i<=cnt;++i)add(fa[i],i);
dfs();
m=read();
while(m--){
scanf("%s",s+1),N=strlen(s+1),l=read(),r=read();
init(),node=1,L=0;
for(register int i=1;i<=N;++i){
if(son(node,s[i]-'a')&&ask(l+L,r,1,n,root[son(node,s[i]-'a')]))node=son(node,s[i]-'a'),++L;
else {
while(L&&(!son(node,s[i]-'a')||!ask(l+L,r,1,n,root[son(node,s[i]-'a')]))){
--L;
if(L==len[fa[node]])node=fa[node];
}
if(!son(node,s[i]-'a')||!ask(l+L,r,1,n,root[son(node,s[i]-'a')]))node=1,L=0;
else node=son(node,s[i]-'a'),++L;
}
insertt(s[i]-'a',L);
}
printf("%lld\n",calc());
}
}
一些闲扯：
关于这道题
它让我写了一个星期，在看了题解后依然抄了三天
让我在二轮后不想去机房，因为一去机房就要继续写这屑题
让我丧失学OI的信心
让我决定立刻结束字符串的学习
让我对曾经认为一辈子都不会学的计算几何产生了兴趣
不过其实这道题对$SAM$的能有更深入的认识吧，也涨了不少姿势。
而且在$loj$上交的时候出现了一个神奇的问题：因为编译出的$exe$过大（$9MB$，我也不知道为啥会这么大啊$QAQ$）不支持运行导致$CE$？
喵喵喵？
