有点厉害。
首先给一个 \(\text{SAM}\) 的做法。我们先对所有串建立 \(\text{SAM}\)，然后对于每个 \(T\)，我们先预处理对于每个节点对应的 \(endpos\) 集合，多长的子串可以满足条件。
然后，我们把 \(S\) 串往当前的自动机输入，每次会来到一个 \(endpos\) 集合。同时再输入的过程中保留 \(curlen\) 表示当前匹配上的长度，如果匹配上了就 \(+1\)，如果失配了就和当前失配节点的 \(len\) 取 \(\min\)，直到匹配上为止。然后我们就得到了 \(S\) 中所有在 \(i\) 位置结束的子串，在当前限制下的可用长度区间。（注意还要和 \(curlen\) 取 \(\min\)，因为那前面的根本在这个限制串匹配不上）
最后将所有的限制区间取交集，得到每个位置可用的答案区间。这还没完，因为我们需要的是原串本质不同的子串，所以需要再建一个 \(\text{SAM}\)，对于同一个 \(endpos\) 集合，长度落在 \(len\) 内的所有贡献，每个 \(endpos\) 集合只计算一次。然后就可以通过了，复杂度 \(O(|S|+n|T|)\)。
struct node{
int len,sz,pa,ss,nxt[26];
node(){
len=0,sz=0,pa=0;
rd(i,26)nxt[i]=0;
}
}s[100005];
vt<int>vv[100005];
int lst,cnt,ss[100005];
inline void add(int c,int v){
int x=lst;s[++cnt]=node();
s[cnt].len=s[lst].len+1;
s[lst=cnt].sz=1;ss[cnt]=v;
for(;x&&!s[x].nxt[c];x=s[x].pa)s[x].nxt[c]=cnt;
if(!x)return (void)(s[cnt].pa=1);
int to=s[x].nxt[c];
if(s[x].len+1==s[to].len){
return(void)(s[cnt].pa=to);
}
s[++cnt]=s[to];
s[cnt].sz=0;
s[cnt].len=s[x].len+1;
for(;x&&s[x].nxt[c]==to;x=s[x].pa)s[x].nxt[c]=cnt;
s[cnt-1].pa=s[to].pa=cnt;
}
int l,r,L[100005],R[100005];
inline void dfs(int x){
for(auto j:vv[x]){
dfs(j);
s[x].sz+=s[j].sz;
ss[x]=ss[j];
}
if(l<=s[x].sz&&s[x].sz<=r){
L[x]=s[s[x].pa].len+1;
R[x]=s[x].len;
}else L[x]=114514,R[x]=0;
}
inline void getcur(int x){
if(x!=1)L[x]=min(L[x],L[s[x].pa]),R[x]=max(R[x],R[s[x].pa]);
for(auto j:vv[x])getcur(j);
}
inline void build(string t){
cnt=1,lst=1,s[1]=node();
rd(i,(int)t.size())add(t[i]-'a',i);
rp(i,cnt)vv[i].clear();
rep(i,2,cnt)vv[s[i].pa].pb(i);
dfs(1);s[1].sz=0;getcur(1);
}
int ans=0;
int ansl[50005],ansr[50005];
inline void solve(int x){
l=s[s[x].pa].len+1,r=R[x]=s[x].len;
l=max(l,ansl[ss[x]]);
r=min(r,ansr[ss[x]]);
ans+=max(0,r-l+1);
for(auto j:vv[x])solve(j);
}
st T,S;
int n,m,cx=0;
inline int trans(int x,int c){
while(x&&!s[x].nxt[c])x=s[x].pa,cx=min(cx,s[x].len);
if(x){
cx++;
return s[x].nxt[c];
}
return 1;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T>>n;
m=T.size();
rd(i,m)ansl[i]=1,ansr[i]=i+1;
rp(_,n){
cin>>S>>l>>r;
if(r>0){
build(S);
cx=0;
for(int x=1,i=0;i<m;i++){
x=trans(x,T[i]-'a');
if(l==0&&L[x]==114514);
else ansl[i]=max(ansl[i],L[x]);
if(l!=0)ansr[i]=min({ansr[i],R[x],cx});
}
}else{
build(S);
cx=0;
for(int x=1,i=0;i<m;i++){
x=trans(x,T[i]-'a');
ansl[i]=max(ansl[i],s[x].len+1);
}
}
}
build(T);
solve(1);
cout<<ans<<endl;
return 0;
}
//Crayan_r
然后是 \(\text{SA}\) 做法。首先把所有的 \(S\) 和 \(T\) 隔着特殊字符连接起来，然后求后缀数组。然后是用高度数组实现的求两个后缀的 \(lcp\)。这都是基本操作。
然后，我们枚举 \(S\) 的后缀，对每个后缀和每条限制，一定存在一个区间 \([L,R]\) 使得这个后缀长度为 \([L,R]\) 的前缀在这个区间内的出现次数满足条件。
我们可以预处理每个 \(T\) 中 \(rnk\) 小于等于某个数的后缀个数。这一步有的选手使用了平衡树维护，实际上是不需要的。我们可以直接记录前缀和，直接得到当前长度的前缀在 \(T\) 中的出现次数。
\(O(1)\) 判断当前长度是否满足要求，我们就可以两次二分分别求出 \([L,R]\)，注意它们两个是独立的，不互相影响。
然后还是合并各个限制答案，我们就得到了对于每个后缀，长度是多少的子串满足要求。
最后就是统计本质不同子串的答案。我们可以在原串上按照排名依次来，当前串 \(i\) 和下一个串 \(i+1\)，所有长度在 \(lcp\) 以内的答案都已经被 \(i\) 统计过了，所以 \(i+1\) 只需要统计 \(lcp\) 以外的部分。这样就不会重复统计子串。
然后就可以通过了。
两种做法的内在联系
实际上我们就是用 \(\text{SA}\) 和 \(\text{SAM}\) 通过相同的中间步骤做着相同的事情。因为 \(\text{SA}\) 和 \(\text{SAM}\) 其实是可以互相替代的。
我们第一个程序用 \(\text{SAM}\) 求出了每个前缀多长的后缀满足要求。第二个程序用 \(\text{LCP}\) 求出了每个后缀多长的前缀满足要求。求法实际上也是相同的。二分 \(lcp\) 长度其实就是在失配树上倍增跳父亲，只不过在 \(\text{SAM}\) 中存在失配树从上往下的关系，并且询问时静态的，所以我们直接从上往下递推了。两者的答案其实是一样的。
后面统计答案的过程就更加相似了。其实一直都是基于查找相同 \(lcp\) 的后缀排名区间来替代 \(endpos\) 集合的作用。两者其实是非常相似的。