题解 P4770 【[NOI2018]你的名字】
zhengrunzhe
2019-07-20 10:01:52
题解里好像都是线段树合并
这里提供一个转化为二维偏序问题然后只用一棵线段树维护的做法
感谢**E_Space**在FJ冬令营的讲解
后缀自动机的**匹配**：**找T的所有前缀中最长的是S子串的后缀**
**双指针扫描法**：
“比如对于T的第i个前缀，匹配的状态为x
设c为T的第i+1个字符
如果xc是S的子串，那么显然T的第i+1个前缀最长的（是S的子串的）后缀是xc
这同时意味着x所在节点有关于c的转移边
于是你只需要将x沿着这条边走一步，再将其长度加上1即可
否则说明T的第i+1个前缀最长的（是S的子串的）后缀比xc短
考虑不断删去xc的首字符，直到它是S的子串为止
这也相当于**不断删去x的首字符，直到它有c的转移边为止**，当然要注意特判删到空以后仍然没有c的转移边的情况
在删首字符的时候注意判断是否要跳到所在节点的父亲，当然你也可以把删去首字符改成**直接跳父亲并修改当前串长度为父亲的len**来节省常数”
——摘自Espace课件
弱化版问题：
**求S和T有多少个本质不同的非空公共子串**
考虑枚举T的每个本质不同的子串询问其是否是S的子串
“先建出T的后缀自动机，然后考虑每个节点接受的字符串中有哪些是S的子串
由于一个节点接受的字符串都是某个子串的后缀，所以我们可以找到这些字符串在T中的一个右端点（即节点的at），然后查询一下T的长度为at的前缀最长的（是S的子串的）后缀的长度len
这样我们就可以知道T的以at为右端点的子串中长度不超过len的都是S的子串，长度大于len的都不是S的子串
于是我们就可以把(0,len]和节点接受字符串长度的区间（即(父亲的max,自己的max]）的交中的整数个数计入答案
至于如何求len，只要预处理的时候建出S的自动机，用T在上面跑一遍就可以了”
——摘自E_Space课件
### [NOI2018]你的名字：
**给定S(Len(S)<=5e5),Q(Q<=1e5)次询问(T,l,r)求T(∑Len(T)<=1e6)和S[l,r]有多少个本质不同的非空子串**
“仍然考虑之前的双指针扫描法，从Lj开始，不断删去其首字符，直到它加上T的第j+1位是S[li:ri]的子串
原先我们的判断方法是判断当前状态所在的节点是否有T(j+1)的转移边
但是现在不能这么判了，因为**转移边指向的状态（如果有的话）是S的子串但不一定是S[li:ri]的子串**
我们的问题是，如何判断一个状态x是否在S[li:ri]中出现
考虑x在S中出现的所有（右端点的）位置，即x所在节点的Right集合
Right集合中什么样的位置p才会让x在S[li:ri]中出现呢？
x在S[li:ri]中出现当且仅当x所在节点的Right集合中存在p使得 **p≤ri 并且 p-len(x)+1≥li**（其中len(x)是x的长度）
那么就是**判断Right集合中不超过ri的p中最大的(p-len(x)+1)是否大于等于li**
当然，(p-len(x)+1)最大当且仅当p最大
这是个经典的**二维偏序**问题
一维是**p≤ri**，另一维是at值为p的节点必须要在x所在节点的子树中（这样Right集合中才会有p）”
对于第一维：把所有询问存下来，离线处理，按照r从小到大排序，然后把S的后缀自动机中所有at<=r的np节点激活，插入到线段树中
对于第二维：建S后缀自动机后 我们把所有节点的fa和它自己连边，形成一棵树,利用树的**dfs序**，我们能将树的一棵子树范围转化成一段区间，从而用线段树求区间最大值
时间复杂度O(∑Len(T) log Len(S))
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
using std::sort;
typedef long long ll;
const int LS=5e5+10,LT=1e6+10,Q=1e5+10;
template<int maxn>struct Suffix_Automaton
{
int son[maxn][26],fa[maxn],back[maxn],right[maxn],len[maxn],last,cnt;
inline const void clear(int p)
{
fa[p]=right[p]=back[p]=len[p]=0;
memset(son[p],0,sizeof(son[p]));
}
inline const void insert(int c,int k)
{
int p=last,np=++cnt;clear(np);
len[last=np]=len[p]+1;back[right[np]=k]=np;
for (;p&&!son[p][c];p=fa[p])son[p][c]=np;
if (!p)return (void)(fa[np]=1);
int q=son[p][c];
if (len[q]==len[p]+1)return (void)(fa[np]=q);
int nq=++cnt;len[nq]=len[p]+1;
memcpy(son[nq],son[q],sizeof(son[q]));fa[nq]=fa[q];
fa[q]=fa[np]=nq;right[nq]=k;
for (;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
}
inline const void build(char *s)
{
int n=strlen(s+1);
for (int i=1;i<=n;i++)insert(s[i]-97,i);
}
inline const void clear()
{
clear(last=cnt=1);
}
inline Suffix_Automaton(){last=cnt=1;}
};
Suffix_Automaton<LS<<1>S,T;
int to[LS<<1],next[LS<<1],head[LS<<1],cnt;
inline const void addedge(int u,int v)
{
next[++cnt]=head[u];to[head[u]=cnt]=v;
}
inline const void build()
{
for (int i=1;i<=S.cnt;i++)if (S.fa[i])addedge(S.fa[i],i);
}
int dfn[LS<<1],end[LS<<1];
inline const void dfs(int p)
{
dfn[p]=++cnt;
for (int i=head[p];i;i=next[i])dfs(to[i]);
end[p]=cnt;
}
class Segment_Tree
{
private:
struct tree
{
int mx;
tree *lson,*rson;
inline const void pushup()
{
mx=max(lson->mx,rson->mx);
}
inline const void update(int l,int r,int pos,int key)
{
if (l==r)return (void)(mx=key);
int mid=l+r>>1;
if (pos<=mid)lson->update(l,mid,pos,key);
else rson->update(mid+1,r,pos,key);
pushup();
}
inline const int query(int l,int r,int L,int R)
{
if (l>R||r<L)return 0;
if (l>=L&&r<=R)return mx;
int mid=l+r>>1;
return max(lson->query(l,mid,L,R),rson->query(mid+1,r,L,R));
}
}*root,memory_pool[LS<<3],*tail;
inline const void build(tree *&p,int l,int r)
{
p=tail++;
if (l==r)return;
int mid=l+r>>1;
build(p->lson,l,mid);
build(p->rson,mid+1,r);
}
public:
inline Segment_Tree(){tail=memory_pool;}
inline const void build(){build(root,1,S.cnt);}
inline const void update(int pos,int key){root->update(1,S.cnt,pos,key);}
inline const int query(int l,int r){return root->query(1,S.cnt,l,r);}
}sgt;
char s[LS],t[LT],*tail=t;
ll ans[Q];
int m;
struct query
{
char *t;int l,r,len,id;
inline query(char *a=0,int b=0,int c=0,int d=0,int e=0):t(a),l(b),r(c),len(d),id(e){}
inline const bool operator<(const query &q)const
{
return r<q.r;
}
}q[Q];
int f[LT];
int main()
{
scanf("%s",s+1);S.build(s);
build();cnt=0;dfs(1);sgt.build();
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int l,r;
scanf("%s%d%d",tail+1,&l,&r);
q[i]=query(tail,l,r,strlen(tail+1),i);
tail+=q[i].len+1;
}
sort(q+1,q+m+1);cnt=1;
for (int i=1;i<=m;i++)
{
for (;cnt<=q[i].r;cnt++)sgt.update(dfn[S.back[cnt]],cnt);
T.build(q[i].t);
int now=1,len=0;
for (int j=1;j<=q[i].len;j++)
{
while (1)
{
if (!now){len=0;now=1;break;}
int nxt=S.son[now][q[i].t[j]-97];
if (!nxt)if (now=S.fa[now],now)len=S.len[now];else;
else {now=nxt;len++;break;}
}
while (1)
{
int mx=sgt.query(dfn[now],end[now]);
if (mx&&mx-len+1>=q[i].l)break;
if (mx&&mx-S.len[S.fa[now]]+1>q[i].l){len=mx-q[i].l+1;break;}
now=S.fa[now];len=S.len[now];
}
f[j]=len;
}
ll nowans=0ll;
for (int j=2;j<=T.cnt;j++)
{
int right=T.right[j],len=T.len[j],flen=T.len[T.fa[j]];
if (f[right]<=flen)nowans+=1ll*len-flen;
else if (f[right]<len)nowans+=len-f[right];
}
ans[q[i].id]=nowans;
T.clear();
}
for (int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}
```