首页 > 其他 > 详细

bzoj5417/luoguP4770 [NOI2018]你的名字(后缀自动机+线段树合并)

时间:2019-12-23 10:25:18      阅读:96      评论:0      收藏:0      [点我收藏+]

bzoj Luogu

给出一个字符串 $ S $ 及 $ q $ 次询问,每次询问一个字符串 $ T $ 有多少本质不同的子串不是 $ S[l,r] $ 的子串。

题解时间

上一道题有点像哈。

只不过这一次是要将 $ T $ 放在 $ S $ 上匹配。

我们先不管每次选取的 $ S $ 段不同,就假设我们已经建好了选取的 $ S $ 段的SAM(也就是前68pts啦)

我们直接把 $ T $ 放上去匹配,维护现在匹配上的最长长度 $ lnow $ ,当 $ px $ 跳到 $ tranc $ 时 $ lnow++ $ ,

当失配时 $ px $ 直接跳到 $ pre $ , $ lnow $ 修改为对应点的 $ len $ 。

但很明显不能每次重新建一遍 $ S $ 的SAM。

所以考虑让上面的匹配操作可以查询在 $ [l,r] $ 区间内某点有无 $ endpos $ 。

写个线段树合并就好。

然后此时上面匹配操作的“失配”步骤需要改一下。

正常是跳到 $ pre $ 后直接修改 $ lnow $ ,但这里不行。

因为:假设我们匹配到某点 $ x $ ,字符串 $ T $ 上 $ ch $ , $ lnow $ 已知,

我们要查询的就是 $ tranc[x][ch] $ 的 $ [l+lnow,r] $ 区间。

所以失配时改成 $ lnow-- $ ,直到 $ lnow==len[pre[x]] $ 时才跳 $ pre $ 。

很明显这样匹配依然是 $ O(nlogn) $ ,那个log来自线段树。

然后就完事了。

设 $ T $ 上匹配第 $ i $ 个字符后的 $ lnow=ma[i] $ ,

则 $ ans=\Sigma (T的SAM上每一个节点) len[x]-max(len[pre[x]],ma[ip[x]]) $

( $ ip[x] $ 指TSAM上 $ x $ 点对应 $ T $ 的哪一位字符)

丑陋的封装-1000

#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
namespace RKK
{
const int N=2000011;
int TAT;
char s0[N],s1[N];int l0,l1;
int rt[N],tcnt,lson[N*44],rson[N*44];
struct sumireko{int to,ne;}e[N];int he[N],ecnt;
void addline(int f,int t){e[++ecnt].to=t;e[ecnt].ne=he[f],he[f]=ecnt;}
void insert(int x,int &px,int pl,int pr)
{
    if(!px) px=++tcnt;
    if(pl==pr) return;
    int pm=pl+pr>>1;
    if(x<=pm) insert(x,lson[px],pl,pm);
    else insert(x,rson[px],pm+1,pr);
}
int merge(int px,int py,int pl,int pr)
{
    if(!px||!py) return px|py;
    int pz=++tcnt;
    if(pl!=pr)
    {
        int pm=pl+pr>>1;
        lson[pz]=merge(lson[px],lson[py],pl,pm);
        rson[pz]=merge(rson[px],rson[py],pm+1,pr);
    }
    return pz;
}
int query(int l,int r,int px,int pl,int pr)
{
    if(l>r||!px) return 0;
    if(l<=pl&&r>=pr) return 1;
    int pm=pl+pr>>1;
    int ret=0;
    if(l<=pm) ret|=query(l,r,lson[px],pl,pm);
    if(r>pm) ret|=query(l,r,rson[px],pm+1,pr);
    return ret;
}
struct remilia{int tranc[26],len,pre;};
int ma[N];
struct sakuya
{
    remilia s[N];
    int ip[N];
    int fin,size;
    sakuya(){fin=size=1;}
    void set(){memset(s,0,sizeof(remilia)*(size+10)),memset(ip,0,sizeof(int)*(size+10)),fin=size=1;}
    void ins(int ch,int i=0)
    {
        int npx,npy,lpx,lpy;
        npx=++size;
        s[npx].len=s[fin].len+1;ip[npx]=i;
        for(lpx=fin;lpx&&!s[lpx].tranc[ch];lpx=s[lpx].pre) s[lpx].tranc[ch]=npx;
        if(!lpx) s[npx].pre=1;
        else
        {
            lpy=s[lpx].tranc[ch];
            if(s[lpy].len==s[lpx].len+1) s[npx].pre=lpy;
            else
            {
                npy=++size;
                s[npy]=s[lpy],ip[npy]=ip[lpy];
                s[npy].len=s[lpx].len+1;
                s[npx].pre=s[lpy].pre=npy;
                while(s[lpx].tranc[ch]==lpy)
                {
                    s[lpx].tranc[ch]=npy;
                    lpx=s[lpx].pre;
                }
            }
        }
        fin=npx;
    }
    void dfs(int x)
    {
        for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to) dfs(t),rt[x]=merge(rt[x],rt[t],1,l0);
    }
    void work()
    {
        for(int i=2;i<=size;i++) addline(s[i].pre,i);
        dfs(1);
    }
}sam,sam1;
void work(int l,int r)
{
    sam1.set();
    for(int i=1;i<=l1;i++) sam1.ins(s1[i]-'a',i);
    int px=1,lnow=0;
    for(int i=1;i<=l1;i++)
    {
        while(px!=1&&!query(l+lnow,r,rt[sam.s[px].tranc[s1[i]-'a']],1,l0))
        {
            lnow--;
            if(lnow==sam.s[sam.s[px].pre].len) px=sam.s[px].pre;
        }
        if(query(l+lnow,r,rt[sam.s[px].tranc[s1[i]-'a']],1,l0))
        {
            lnow++;
            px=sam.s[px].tranc[s1[i]-'a'];
        }
        ma[i]=lnow;
    }
    lint ans=0;
    for(int i=2;i<=sam1.size;i++) ans+=max(0,sam1.s[i].len-max(sam1.s[sam1.s[i].pre].len,ma[sam1.ip[i]]));
    printf("%lld\n",ans);
    memset(ma,0,sizeof(int)*(l1+5));
}
int Iris()
{
    scanf("%s",s0+1),l0=strlen(s0+1);
    for(int i=1;i<=l0;i++) sam.ins(s0[i]-'a'),insert(i,rt[sam.fin],1,l0);
    sam.work();
    scanf("%d",&TAT);
    for(int rkk=1,l,r;rkk<=TAT;rkk++)
    {
        scanf("%s%d%d",s1+1,&l,&r),l1=strlen(s1+1);
        work(l,r);
    }
    return 0;
}
}
int main(){return RKK::Iris();}

bzoj5417/luoguP4770 [NOI2018]你的名字(后缀自动机+线段树合并)

原文:https://www.cnblogs.com/rikurika/p/12079303.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!