题解 P4770 【[NOI2018]你的名字】
shadowice1984
2018-12-30 20:04:14
显然这种后缀自动机duliu题几句话是说不清的……
所以我们还是来慢慢分析这题的性质好了
____________________
### 前置芝士:后缀自动机(sam)
蛤？做noi的字符串题不会sam,建议出门左转你站模板区学习一下
### 前置芝士:线段树合并
很多题目都是后缀自动机和线段树合并套在一起进行的，这是因为线段树合并这个算法可以很方便的维护后缀自动机的right集合，如果你不会线段树合并的话，可以翻一翻往期的咕咕日报，有非常详细的讲解
不过值得注意的是这道题用的线段树合并和大家惯用的合并写法不是很一致，后面会具体讲这部分内容
_____________________
# 本题题解
先来重新描述一下模糊不清的题意
给定一个模板串$S$,多组询问,每次给出一个询问字符串$T$和一个区间$(l,r)$
要求你输出$T$有多少个**本质不同**的子串,满足这个子串没有在S的$(l,r)$这段区间当中出现
然后我们接着转化一波就是询问你有几个T的本质不同的子串满足这个子串在$S$的给定区间当中出现了，然后我们求出这个东西之后拿T的所有本质不同子串去减就能得到答案了(如果连求T本质不同子串数目这点都不会的建议重新学一遍sam)
对于这题来讲我们先来考虑几个比较特殊的部分分再来解决最后的问题会比较有效，所以让我们一个部分分一个部分分的解决这题
## Case1:$l=1,r=|S|$
这样的话我们可以先对字符串$S$建一个后缀自动机然后对询问串$T$建一个后缀自动机，由于$T$的总长不是特别长因此我们的复杂度是对的
接下来为了做这道题我们需要知道一个知识，就是给定一个模板串$S$和一个匹配串$T$，现在我们希望对于$T$的每一个前缀$(1,i)$求出一个最长的字符串P，满足P是$(1,i)$的后缀并且$P$是S的子串
通俗点说就是把$T$放到$S$上去跑匹配
那么其实这个东西也十分的简单，我们仔细观察一下parent树的性质就会发现parent树的性质和ac自动机的fail树性质相当的像，甚至我们可以说sam其实就是把一个字符串的所有子串抽出来建了一个ac自动机
那么我们向前添加一个字符的时候只需要看sam上对应的节点有没有对应的出边:
如果有对应的出边我们直接走上去并且让匹配长度+1,
否则我们**不停的跳parent树**直到parent树上一个节点有对应的出边为止，此时我们把匹配长度更新为parent树上节点len值+1。
如果跳到了根依然失配那么我们将匹配长度更新为0
这样我们就求出了$T$的每一个前缀的匹配长度了
那么我们有了这个匹配长度之后有什么用呢？
我们在T的后缀自动姬的每一个节点上维护一个ans值表示这个节点的最长合法长度,
解释一下ans的含义就是这样
我们知道给定一个后缀自动机节点再给定一个字符串长度可以唯一确定一种本质不同子串,那么一个节点的ans值就表示所有长度小于ans并且也被这个节点表示的字符串都是S的子串
我们在S的后缀自动机上跑匹配的同时我们也在T的后缀自动机上跑T这个串,并且每次匹配串的长度减小的时候我们在T的parent树上跳直到这个节点的len值变的合法,然后用当前匹配的长度去更新这个点到根路径上节点的ans值
显然暴力跳链复杂度是假的，但是我们发现当一个点的ans值等于len值的时候这个节点的祖先的ans值也全部等于len值，因此我们暴力跳链如果这个点的ans值等于len我们就停止跳链，这样复杂度就真了
最后的答案就是所有点ans值-父亲的len值之和了，当然由于我们做了个补集转化还要用本质不同的子串数目减去我们求出的数才能输出
### Case2:l,r任意
我们发现其实我们只要知道$(l,r)$这段区间的后缀自动机长什么样就可以直接执行上面的算法了，但是问题是我们没有办法轻松的得知一个区间的后缀自动机
但是仔细想想我们上面算法流程真的需要后缀自动机本身吗？
其实并不是，我们只是借助S的后缀自动机求出了T的每个前缀的匹配长度
我们在$L=1,r=|S|$所用的算法仅仅对S的后缀自动机执行了这样几个操作
1.检查S的一个节点是否有某一个字符的出边，如果有那就转移上去
2.跳parent树
3.读取一个节点的len值
换句话说我们如果能够实现上面几个操作，并且保证我们读取的len值是这个节点在以$(l,r)$这个区间为模板串意义下的len,转移到的节点也是这个节点在$(l,r)$意义下的出边，我们的算法就还是对的
现在我们来考虑如何实现这几个操作
我们使用线段树合并来维护每一个后缀自动机节点的right集合，线段上维护的是区间最大值
当我们判断是否存在一条在$(l,r)$意义下指向p的转移边的时候，我们只需要查找节点p的righ集合在$(1,r)$的区间最大值然后和l进行比较如果这个最大值比$l$小就证明这个转移边在$(l,r)$作为模板串的时候并不合法，不能进行转移
同样的，当我们读取一个节点的len值的时候我们还是找出$(1,r)$的区间最大值,在$(l,r)$作为模板串的意义下，这个节点的len值应该是$\min(len,l-maxpos(1,r)+1)$
至于跳parent树的过程，我们仔细研究一下parent树的定义就会发现其实在整个大的后缀自动机上跳就肥肠符合我们的需要了，所以跳原来后缀自动机上的parent树即可
然后我们发现这里的线段树合并和我们平常写的可能不是很一样，平常我们合并两个线段树的时候是将某一个线段树插入到另一个线段树里，然后我们一般的套路是一边在树上dfs一边合并线段树，然后当我们dfs到节点u的时候我们就get到u子树中的信息
那么我们会发现当我们按照平常的线段树合并算法合并两个线段树u和v的时候原来的两个线段树都会**被销毁**
您可能一开始像我一样naive的认为我们在线段树合并的时候是把u的一些孩子指针指向了v线段树，所以被销毁的只有u线段树而没有v线段树
然鹅这种想法是相当错误的，当我们合并了u和v之后v的一些节点就成为了u线段的一部分，如果此时我们把u和另外一个线段树v'合并,那么同时属于u和v的线段树节点就会被修改，此时v就相当于被销毁了
为了避免这种尴尬的情况发生(显然如果出现这个bug你会看着线段树合并的代码挠半天头而依然不知所措，并且小数据你有很大的概率wa不了)我们需要将线段树合并的过程**可持久化**
具体来讲每次我们需要修改u节点的孩子指针的时候我们新开一个节点然后把这个节点的孩子指针指向合并左子树和右子树产生的节点，这样我们就保留了每一个版本的线段树，此时我们就可以读取任意一个节点的right集合了~
代码的话不是很好写，细节也比较多，请注意封装和细节的分类讨论
上代码~
```C
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e6+10;typedef long long ll;char mde[N];int n;int nl;int nr;int m;
struct suffixautomaton//简易后缀自动机板子
{
int mp[N][27];int ct;int fa[N];int len[N];int n;
inline int& operator [](const int& x){return len[x];}
inline void ih(int x){n=x;for(int i=1;i<=n;i++)len[i]=i;ct=n+1;}
inline void clr()
{
for(int i=1;i<=ct;i++)for(int j=1;j<=26;j++)mp[i][j]=0;
for(int i=1;i<=ct;i++)fa[i]=0;for(int i=1;i<=ct;i++)len[i]=0;
}
inline void ins(int x,int c)
{
int p=(x==1)?n+1:x-1;for(;p&&mp[p][c]==0;p=fa[p])mp[p][c]=x;
if(p==0){fa[x]=n+1;return;}int q=mp[p][c];
if(len[q]==len[p]+1){fa[x]=q;return;}len[++ct]=len[p]+1;
for(int i=1;i<=26;i++)mp[ct][i]=mp[q][i];
for(;p&&mp[p][c]==q;p=fa[p])mp[p][c]=ct;fa[ct]=fa[q];fa[q]=fa[x]=ct;
}
};
namespace SM
{
suffixautomaton sam;int s[40*N][2];int va[40*N];int cnt;
int v[N];int x[N];int al[N];int ct;
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
# define mov(p,c) (p=sam.mp[p][c])
# define jup(p) (p=sam.fa[p])
inline void ins(int p,int l,int r,int pos)
{
va[p]=pos;if(r-l==1){return;}int mid=(l+r)/2;
if(pos<=mid)ins(s[p][0]=++cnt,l,mid,pos);else ins(s[p][1]=++cnt,mid,r,pos);
}
inline int mg(int p1,int p2,int isr)//这里的合并是可持久化的，不会销毁任意一颗线段树
{
int nw=(isr)?p1:++cnt;
if(s[p1][0]&&s[p2][0])s[nw][0]=mg(s[p1][0],s[p2][0],0);
else s[nw][0]=(s[p2][0])?s[p2][0]:s[p1][0];
if(s[p1][1]&&s[p2][1])s[nw][1]=mg(s[p1][1],s[p2][1],0);
else s[nw][1]=(s[p2][1])?s[p2][1]:s[p1][1];
va[nw]=max(va[s[nw][0]],va[s[nw][1]]);return nw;
}
inline int qry(int p,int l,int r,int dl,int dr)//查询区间最大值
{
if((p==0)||(dl==l&&r==dr))return va[p];int mid=(l+r)/2;int res=0;
if(dl<mid)res=max(res,qry(s[p][0],l,mid,dl,min(dr,mid)));
if(mid<dr)res=max(res,qry(s[p][1],mid,r,max(dl,mid),dr));
return res;
}
inline void dfs(int u){for(int i=al[u];i;i=x[i])dfs(v[i]),mg(u,v[i],1);}
inline void build()
{
sam.ih(n);for(int i=1;i<=n;i++)sam.ins(i,mde[i]-'a'+1);
cnt=sam.ct;for(int i=1;i<=sam.ct;i++)add(sam.fa[i],i);
for(int i=1;i<=n;i++)ins(i,0,n,i);dfs(n+1);
}
inline void trs(int& p,const int& c,int& len)//暴力跳fail树进行转移
{
for(;p!=n+1;jup(p),len=sam[p])
if(sam.mp[p][c])
{
int mle=qry(sam.mp[p][c],0,n,0,nr)-nl+1;
if(sam[sam.fa[p]]<mle){len=min(len+1,mle);mov(p,c);return;}
}
if(p==n+1&&(sam.mp[p][c]==0||qry(sam.mp[p][c],0,n,0,nr)<nl)){len=0;return;}
mov(p,c);len++;
}
# undef mov
# undef jup
}
namespace SM2
{
suffixautomaton sam;char mde[N];int le;
int v[N];int x[N];int al[N];int ct;int mx[N];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
# define mov(p,c) (p=sam.mp[p][c])
# define jup(p) (p=sam.fa[p])
inline void build()
{
for(int i=1;i<=sam.ct;i++)al[i]=0;ct=0;sam.clr();scanf("%s",mde+1);
scanf("%d%d",&nl,&nr);le=1;for(;mde[le+1]!='\0';le++);sam.ih(le);
for(int i=1;i<=le;i++)sam.ins(i,mde[i]-'a'+1);
for(int i=1;i<=sam.ct;i++)add(sam.fa[i],i),mx[i]=sam[sam.fa[i]];
}
inline void aju(int p,const int& lim)//打标记
{
for(;p!=le+1&&sam[sam.fa[p]]>=lim;jup(p));
for(;p!=le+1&&sam[p]>mx[p];jup(p))mx[p]=max(mx[p],min(sam[p],lim));
}
inline ll dfs(int u)
{ll ret=0;for(int i=al[u];i;i=x[i])ret+=mx[v[i]]-sam[u]+dfs(v[i]);return ret;}
inline ll dfs2(int u)
{ll ret=0;for(int i=al[u];i;i=x[i])ret+=sam[v[i]]-sam[u]+dfs2(v[i]);return ret;}
inline void solve(int z)
{
for(int i=1,p1=n+1,p2=le+1,nle=0;i<=le;i++)
mov(p2,mde[i]-'a'+1),SM::trs(p1,mde[i]-'a'+1,nle),aju(p2,nle);
printf("%lld\n",dfs2(le+1)-dfs(le+1));
}
# undef mov
# undef jup
}
int main()
{
scanf("%s",mde+1);for(n=1;mde[n+1]!='\0';n++);SM::build();scanf("%d",&m);
for(int i=1;i<=m;i++)SM2::build(),SM2::solve(i);return 0;//拜拜程序~
}
```