给出一个字符串\(S\),有\(q\)组询问,每次询问给出一个字符串\(T\)和整数\(l,r\).问能从\(T\)中选出多少个本质不同的子串,满足这个子串在\(S\)的区间\([l,r]\)没有出现过。
\(|S| \leq 5 \times 10^5,q \leq 10^5,\sum|T| \leq 5 \times 10^5\)
AC这道题的一瞬间,我感觉和后缀自动姬合二为一,达到了生命的大和谐。
考虑一个简化的问题,只考虑\(T\)和整个\(S\)串的答案。
把\(S\)和\(T\)都建出后缀自动机,记为\(M_1\)和\(M_2\).然后把\(T\)串放到\(M_1\)上匹配,记录当前节点\(x_1\)和匹配长度\(matlen\),然后还要记录在\(M_2\)上走到的节点\(x_2\). 对于节点\(x_2\),它贡献的本质不同的串的长度应该在\([len(link(x_2))+1,len(x_2)]\),个数就是区间长度. 但是还要考虑到如果不能与\(S\)匹配,所以如果\(matlen\)落在\([len(link(x_2))+1,len(x_2)]\),贡献的本质的长度范围应该是\([matlen+1,len(x_2)]\).
因此我们对\(M_2\)的每个节点维护一个值\(mlen\)表示该节点与\(S\)的最大匹配长度。每次用matlen去更新答案。更新方法是沿着link树往上跳,设跳到的节点为\(y\),如果\(matlen<len(link(y)+1)\),那么mlen不变,增加的子串个数为\(mlen-len(link(y))\).否则更新\(mlen\)为\(matlen\),增加的子串个数为\(matlen-len(link(y))\).
如何求区间\(S[l,r]\)内的字符与\(T\)匹配的结果呢?我们可以用到\(right\)集合。如果\(M_1\)的\(right\)集合中存在落在当前需要匹配的区间\([l+matlen,r]\)中,那么匹配长度\(matlen\)就可以+1. 否则也是沿着\(link\)往上跳即可。\(right\)集合可以用权值线段树维护,预处理的时候用线段树合并,查询的时候就是一个区间求和。
细节比较多,见代码注释
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxc 26
#define maxn 1000000
#define maxlogn 30
using namespace std;
int n,q;
char s[maxn+5],t[maxn+5];
struct segment_tree{
#define lson(x) (tree[x].ls)
#define rson(x) (tree[x].rs)
struct node{
int ls;
int rs;
int val;
}tree[maxn*maxlogn+5];
int ptr=0;
void push_up(int x){
tree[x].val=tree[lson(x)].val+tree[rson(x)].val;
}
void update(int &x,int upos,int l,int r){
x=++ptr;
if(l==r){
tree[x].val++;
return;
}
int mid=(l+r)>>1;
if(upos<=mid) update(lson(x),upos,l,mid);
else update(rson(x),upos,mid+1,r);
push_up(x);
}
int query(int x,int L,int R,int l,int r){
if(x==0||L>R) return 0;
if(L<=l&&R>=r) return tree[x].val;
int mid=(l+r)>>1;
int ans=0;
if(L<=mid) ans+=query(lson(x),L,R,l,mid);
if(R>mid) ans+=query(rson(x),L,R,mid+1,r);
return ans;
}
int merge(int x,int y){
if(!x||!y) return x+y;
int now=++ptr;//这样合并不会影响原来的两棵树,类似可持久化
tree[now].val=tree[x].val+tree[y].val;
lson(now)=merge(lson(x),lson(y));
rson(now)=merge(rson(x),rson(y));
return now;
}
#undef lson
#undef rson
}Tr;
struct SAM{
#define link(x) t[x].link
#define len(x) t[x].len
struct node{
int ch[maxc];
int link;
int len;
int mlen;//该位置代表的后缀向前最长的合法长度(没有和S匹配)
int root;//代表的right集合对应的线段树的根节点
void clear(){
//因为要多次重建自动机,做好初始化
for(int i=0;i<maxc;i++) ch[i]=0;
link=len=root=0;
}
}t[maxn*2+5];
const int root=1;
int last=root;
int ptr=1;
inline int size(){
return ptr;
}
void ini(){
last=root;
ptr=1;
t[root].clear();
}
int New(){
ptr++;
t[ptr].clear();
return ptr;
}
inline int delta(int x,int c){
return t[x].ch[c];//转移函数
}
void extend(int c,int pos){
int p=last,cur=New();
len(cur)=len(p)+1;
if(pos) Tr.update(t[cur].root,pos,1,n);//因为并不需要T的right集合,插入T的时候把pos设为0
while(p&&t[p].ch[c]==0){
t[p].ch[c]=cur;
p=link(p);
}
if(p==0) link(cur)=root;
else{
int q=t[p].ch[c];
if(len(p)+1==len(q)) link(cur)=q;
else{
int clo=New();
len(clo)=len(p)+1;
for(int i=0;i<maxc;i++) t[clo].ch[i]=t[q].ch[i];
link(clo)=link(q);
link(q)=link(cur)=clo;
while(p&&t[p].ch[c]==q){
t[p].ch[c]=clo;
p=link(p);
}
}
}
last=cur;
}
void topo_sort(){
static int in[maxn+5];
queue<int>q;
for(int i=1;i<=ptr;i++) in[link(i)]++;
for(int i=1;i<=ptr;i++) if(!in[i]) q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
if(link(x)==0) continue;
in[link(x)]--;
t[link(x)].root=Tr.merge(t[link(x)].root,t[x].root);
if(in[link(x)]==0) q.push(link(x));
}
}
}S1,S2;
long long calc(char *t,int l,int r){
int lent=strlen(t+1);
S2.ini();
for(int i=1;i<=lent;i++) S2.extend(t[i]-'a',0);
for(int i=1;i<=S2.size();i++) S2.t[i].mlen=S2.t[i].len;
int x1=S1.root,x2=S2.root;
int matlen=0;//S[l,r]与T的匹配长度
long long ans=0;
for(int i=1;i<=lent;i++){
int c=t[i]-'a';
x2=S2.delta(x2,c);
if(S1.delta(x1,c)&&Tr.query(S1.t[S1.delta(x1,c)].root,l+matlen,r,1,n)){
//如果S串的ch[x][c]对应的right集合中,有被当前需要匹配的范围[l+tot,r]包含的,就说明当前的T与S[l,r]匹配长度+1.
x1=S1.t[x1].ch[c];
matlen++;
}else{
while(x1&&!(S1.delta(x1,c)&&Tr.query(S1.t[S1.delta(x1,c)].root,l+matlen,r,1,n))){//不能匹配,跳link
if(matlen==0){
x1=0;
break;
}
matlen--;//减少匹配长度,尝试卡进区间内
if(matlen==S1.len(S1.link(x1))) x1=S1.link(x1);
}
if(!x1){
x1=S1.root;
matlen=0;
}else{
x1=S1.delta(x1,c);
matlen++;
}
}
for(int y=x2;y;y=S2.link(y)){
if(matlen>S2.len(S2.link(y))){//匹配位置在当前节点代表的串[len(link(x))+1,len(x)]内
ans+=S2.t[y].mlen-matlen;
S2.t[y].mlen=matlen;
break;//此时对祖先节点已经没有影响,可以break
}else{//否则这整个区间都是合法的
ans+=S2.t[y].mlen-S2.len(S2.link(y));
S2.t[y].mlen=S2.len(S2.link(y));//这一部分的贡献已经计算过了,要移到前面
}
}
// printf("i=%d x1=%d x2=%d,ans=%lld\n",i,x1,x2,ans);
}
// printf("----\n");
return ans;
}
int main(){
#ifndef LOCAL
freopen("name.in","r",stdin);
freopen("name.out","w",stdout);
#endif
int l,r;
scanf("%s",s+1);
n=strlen(s+1);
S1.ini();
for(int i=1;i<=n;i++) S1.extend(s[i]-'a',i);
S1.topo_sort();
scanf("%d",&q);
for(int i=1;i<=q;i++){
scanf("%s",t+1);
scanf("%d %d",&l,&r);
printf("%lld\n",calc(t,l,r));
}
}
/*
abc
1
cad 2 3
*/原文：https://www.cnblogs.com/birchtree/p/12416613.html