在打网络同步赛的时候自己还不会后缀自动机，这题就写了个hash暴力滚粗。
为了提高自己的姿势水平，就学习了后缀自动机。
首先，这题的68分算法十分好想，有很多种写法。
100分算法的流程如下：
1.对S串建后缀自动机，线段树合并求出每个点的right集合
2.对读入的T串在S的自动机上跑，尽可能地跳fa，直到p所代表的某个串在S的区间中出现过，给其打上标记
3.将t插入后缀自动机，用标记维护答案。
代码：
#include <bits/stdc++.h> using namespace std; const int _S_=500010,INF=INT_MAX>>2; namespace sama{ struct p{ int trans[26],fa,ml,val; }sa[_S_*2]; int tot,la,in[_S_*2]; void init(){ la=1; for (int i=1; i<=tot; ++i) memset(sa[i].trans,0,sizeof(sa[i].trans)); tot=1; } void insert(int c,int v){ int np=++tot,p=la; sa[np].ml=sa[la].ml+1; for (; p&&!sa[p].trans[c]; p=sa[p].fa) sa[p].trans[c]=np; if (p){ int q=sa[p].trans[c]; if (sa[q].ml==sa[p].ml+1) sa[np].fa=q; else{ int nq=++tot; sa[nq].ml=sa[p].ml+1; sa[nq].val=sa[q].val; memcpy(sa[nq].trans,sa[q].trans,sizeof(sa[q].trans)); sa[nq].fa=sa[q].fa; sa[q].fa=sa[np].fa=nq; for (; p&&sa[p].trans[c]==q; p=sa[p].fa) sa[p].trans[c]=nq; } } else sa[np].fa=1; sa[la=np].val=v; } long long query(){ long long ans=0; for (int i=1; i<=tot; ++i) if (sa[i].ml>sa[i].val) ans+=sa[i].ml-max(sa[i].val,sa[sa[i].fa].ml); return ans; } } int la=1,tot=1,l,sl,sr,cc,trans[_S_*2][26],ml[_S_*2],fa[_S_*2],in[_S_*2]; void append(int c){ int np=++tot,p=la; ml[np]=ml[la]+1; for (; p&&!trans[p][c]; p=fa[p]) trans[p][c]=np; if (p){ int q=trans[p][c]; if (ml[q]==ml[p]+1) fa[np]=q; else{ int nq=++tot; ml[nq]=ml[p]+1; memcpy(trans[nq],trans[q],sizeof(trans[q])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; for (; p&&trans[p][c]==q; p=fa[p]) trans[p][c]=nq; } } else fa[np]=1; la=np; } namespace segmenttree{ const int NODE=_S_*20*2; int rt[_S_*2],ll,rr,num; struct node{ int l,r,v; }T[NODE]; #define M int mid=(l+r)>>1 #define L (T[ind].l,l,mid) #define R (T[ind].r,mid+1,r) inline void pushup(int x){ T[x].v=(T[x].l?(T[x].r?max(T[T[x].l].v,T[T[x].r].v):T[T[x].l].v):T[T[x].r].v); } inline void insert(int &ind,int l,int r){ if (!ind) ind=++num; if (l==r) return void(T[ind].v=ll); M; ll<=mid?insert L:insert R; pushup(ind); } inline int ask(int ind,int l,int r){ if (!ind) return -INF; if (ll<=l&&r<=rr) return T[ind].v; M; return ll<=mid?(mid<rr?max(ask L,ask R):ask L):ask R; } inline int merge(int x,int y){ if (!(x&&y)) return x^y; int ind=++num; T[ind].l=merge(T[x].l,T[y].l); T[ind].r=merge(T[x].r,T[y].r); pushup(ind); return ind; } } using namespace segmenttree; void topsort(){ queue<int> q; for (int i=1; i<=tot; ++i) in[i]=0; for (int i=1; i<=tot; ++i) ++in[fa[i]]; for (int i=1; i<=tot; ++i) if (!in[i]) q.push(i); while (!q.empty()){ int x=q.front(); q.pop(); if (fa[x]){ rt[fa[x]]=merge(rt[fa[x]],rt[x]); if (!--in[fa[x]]) q.push(fa[x]); } } } void walk(int c){ int p=la,t=-INF,ban=-INF; for (; p&&!trans[p][c]; p=fa[p]) l=ml[fa[p]]; if (p){ p=trans[p][c]; ++l; while (p>1){ ll=sl+ml[fa[p]]; rr=sr; if (ll<=rr&&(t=ask(rt[p],1,cc))!=-INF) break; p=fa[p]; l=ml[p]; } ban=min(t-sl+1,l); } else p=1; la=p; sama::insert(c,ban); } char s[_S_]; int main(){ freopen("name.in","r",stdin); freopen("name.out","w",stdout); ios::sync_with_stdio(0); cin>>(s+1); cc=strlen(s+1); for (int i=1; s[i]; ++i){ append(s[i]-'a'); ll=i; insert(rt[la],1,cc); } topsort(); int q; cin>>q; while (q--){ cin>>(s+1)>>sl>>sr; la=1; l=0; ll=0; sama::init(); for (int i=1; s[i]; ++i) walk(s[i]-'a'); cout<<sama::query()<<endl; } }
具体实现的时候有一些细节，比如最长的在S中出现的串长不能超过T在S中的匹配长度，初始值的设定等。
另外，之所以T在跳S的后缀自动机的fa时，可以直接修改当前节点，是因为如果一个节点代表的所有串当前没有出现在S的指定区间出现过且最小串长大于1，那么加入一个新字符后也不可能出现。
如果最小串长等于1，显然一直跳到root也没有什么问题。
在开动态开点线段树的空间时，很容易忽略掉线段树合并所带来的常数2，需要小心。
sam能做的事情好多啊！