题解 P4770 【[NOI2018]你的名字】

· · 题解

题解里好像都是线段树合并

这里提供一个转化为二维偏序问题然后只用一棵线段树维护的做法

感谢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))

#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;
}