因为做的题太少所以不放在 SAM 集合里了捏，有时间（可能没时间） 会补一个集合。
题意：给 \(S\) 串和 \(T\) 串，和 \(l_i,r_i\) ，求 \(T\) 中有多少子串和 \(S[l_i,r_i]\) 中的任意一个子串不同。多组询问，\(\sum|T|\leq 10^5\)
考虑如果没有 \(l_i,r_i\) 的限制该怎么做。可以先对 \(S\) 建 SAM，然后用 \(T\) 在 SAM 上跑匹配。求出 \(c_i\) 表示 \(T[1,i]\) 中在 \(S\) 中能匹配的最长后缀。\(i-c_i+1\sim i\) 到 \(i\) 这段的都不行了。
这样看似可以，实际错误。因为没有考虑到 \(T\) 中的重复子串。
考虑这一点就是对 \(T\) 建出 SAM，对于每一个位置，都在 \(T\) 的 SAM 里找到对应节点，就是每一个位置所在的状态都要被记录上。然后在 T 的 SAM 上遍历每一个状态。这个状态里的 \(len_i-\max{(len_{fa},c_{pos})}\) 就是能造成的贡献。这个状态本身能贡献的就是 len 减掉 fa 的 len。而如果被叉掉的长度在这个状态表达的范围内，也要减掉比它小的贡献。
这是没有 l 和 r 询问的。
而如果有的话，就是个套路。用可持久化线段树合并，找到每一个点对应的 endpos 集合。集合里如果有当前查询区间 \(l-len+1\sim r\) 的endpos就可以转移。len的含义是当前 \(T\) 在 \(S\) 中匹配的最大后缀长度。然后就像上面一样做就行。
其实想明白之前挺煎熬的，想明白就挺简单的。
/*
／＞ フ
| _ _|
／`ミ _x 彡
/ |
/ ヽ /
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4000020;
char S[maxn],T[maxn];
int n,m;
int rt[maxn];
namespace SGT
{
int lson[maxn*10],rson[maxn*10],tot;
void update(int l,int r,int x,int &p)
{
if(!p) p=++tot;
if(l==r) return;
int mid=(l+r)>>1;
if(x<=mid) update(l,mid,x,lson[p]);
else update(mid+1,r,x,rson[p]);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
int rt=++tot;
lson[rt]=merge(lson[x],lson[y]);
rson[rt]=merge(rson[x],rson[y]);
return rt;
}
int query(int l,int r,int x,int y,int p)
{
if(l>r||!p||x>y) return 0;
if(x<=l&&y>=r) return 1;
int mid=(l+r)>>1;int ret=0;
if(x<=mid) ret+=query(l,mid,x,y,lson[p]);
if(y>mid) ret+=query(mid+1,r,x,y,rson[p]);
return ret;
}
}
int pos[maxn];
struct SAM
{
struct node
{
int fa,len,tag;
map<char,int> nxt;
}st[maxn];
int sz,lst;
void add(char c,int idx)
{
int cur=++sz; pos[idx]=cur; st[cur].len=st[lst].len+1;
st[cur].tag=st[cur].len;
if(idx) SGT::update(1,n,idx,rt[cur]);
int p=lst;
while(p!=-1&&!st[p].nxt.count(c)) st[p].nxt[c]=cur,p=st[p].fa;
if(p==-1)
st[cur].fa=1;
else
{
int q=st[p].nxt[c];
if(st[q].len==st[p].len+1) st[cur].fa=q;
else
{
int clone=++sz;
st[clone].len=st[p].len+1;
st[clone].nxt=st[q].nxt; st[clone].fa=st[q].fa;
st[clone].tag=st[q].tag;
while(p!=-1&&st[p].nxt[c]==q) st[p].nxt[c]=clone,p=st[p].fa;
st[q].fa=st[cur].fa=clone;
}
}
lst=cur;
}
void clear()
{
for(int i=1;i<=sz;i++) st[i].fa=st[i].len=0,st[i].nxt.clear();
sz=1; lst=1;
st[1].len=0; st[1].fa=-1;
}
}Ssam,Tsam;
int to[maxn],nxt[maxn],head[maxn],num;
void add(int x,int y){num++;to[num]=y;nxt[num]=head[x];head[x]=num;}
void dfs(int p)
{
for(int i=head[p];i;i=nxt[i])
dfs(to[i]), rt[p]=SGT::merge(rt[to[i]],rt[p]);
}
int chk[maxn];
void match()
{
int L,R;scanf("%d%d",&L,&R);
int p=1; int ls=0;
for(int i=1;i<=m;i++)
{
Tsam.add(T[i],0);
while(1)
{
if(p!=-1&&Ssam.st[p].nxt.count(T[i])&&SGT::query(1,n,L+ls,R,rt[Ssam.st[p].nxt[T[i]]]))
{
ls++; p=Ssam.st[p].nxt[T[i]];
break;
}
if(!ls) break; ls--;
if(ls==Ssam.st[Ssam.st[p].fa].len) p=Ssam.st[p].fa;
}
chk[i]=ls;
}
ll ans=0;
for(int i=2;i<=Tsam.sz;i++)
ans+=max(0,Tsam.st[i].len-max(Tsam.st[Tsam.st[i].fa].len,chk[Tsam.st[i].tag]));
printf("%lld\n",ans);
}
int main()
{
//freopen("name.in","r",stdin);
//freopen("name.out","w",stdout);
scanf("%s",S+1); n=strlen(S+1);
Ssam.clear();
for(int i=1;i<=n;i++)
Ssam.add(S[i],i);
for(int i=2;i<=Ssam.sz;i++) add(Ssam.st[i].fa,i);
dfs(1);
int test; scanf("%d",&test);
while(test--)
{
scanf("%s",T+1); m=strlen(T+1);
Tsam.clear();
match();
}
}