E. Forensic Examination

http://codeforces.com/problemset/problem/666/E

题目大意：给模式串S以及m个特殊串，q个询问，询问S的子串[pl,pr]在特殊串编号属于[l,r]中出现次数最多的次数以及在哪个特殊串。

一开始打算用S建SAM，特殊串去匹配。。。测样例时才想起这样不对。胡搞一番后，才开始写下面的做法。

S与特殊串连在一起建SAM，记录S串[1,x]在SAM上节点位置，用来子串定位。每个节点的{right}该串出现的所有地方。于是题目成了求一个节点的{right}中属于某个特殊串次数最多的特殊串。给这些{right}染色，即标记属于哪个特殊串。一个节点用一棵线段树维护最值，然后用线段树合并求出每个节点的线段树。

复杂度O(nlogn)。。。这n大概为10⁶

#include<cstdio>

#include<cmath>

#include<cstring>

const int len(),lem(),N();

struct Node{int pre,nx[],step;}sam[N*+];

int top=,now=,root=,last,lastson;int n,pos[len+];

int m,q,leng,l,r,pl,pr;char str[len+];

int f[][N*+],logg;

struct SegMent{int nx[];unsigned short int big,pos;}tree[lem+];

int stot,rt[N*+];

struct data{unsigned short int x,y;};

void extend(int x)

{

    last=now;now=++top;sam[now].step=sam[last].step+;

    for(;!sam[last].nx[x]&&last;last=sam[last].pre)

        sam[last].nx[x]=now;

    if(!last)sam[now].pre=root;

    else

    {

        lastson=sam[last].nx[x];

        if(sam[lastson].step==sam[last].step+)sam[now].pre=lastson;

        else

        {

            sam[++top]=sam[lastson];sam[top].step=sam[last].step+;

            sam[now].pre=sam[lastson].pre=top;

            for(;sam[last].nx[x]==lastson&&last;last=sam[last].pre)

                sam[last].nx[x]=top;

        }

    }

}

void update(int k)

{

    int next;

    if(tree[tree[k].nx[]].big>tree[tree[k].nx[]].big||

    (tree[tree[k].nx[]].big==tree[tree[k].nx[]].big&&

    tree[tree[k].nx[]].pos<tree[tree[k].nx[]].pos))next=;

    else next=;

    tree[k].big=tree[tree[k].nx[next]].big;

    tree[k].pos=tree[tree[k].nx[next]].pos;

}

void insert(int &k,int l,int r,int x)

{

    if(!k)k=++stot;

    if(l==r){tree[k].big++;tree[k].pos=x;return;}

    int mid=(l+r)>>;

    if(x<=mid)insert(tree[k].nx[],l,mid,x);

    else insert(tree[k].nx[],mid+,r,x);

    update(k);

}

int find(int l,int r)

{

    int x=pos[r];

    for(int j=logg;j>=;j--)

    if(sam[f[j][x]].step>=r-l+)x=f[j][x];

    return x;

}

int merge(int x,int y,int l,int r)

{

    if(!x||!y)return x|y;

    int z=++stot;

    if(l==r){tree[z].big=tree[x].big+tree[y].big;tree[z].pos=tree[x].pos;return z;}

    int mid=(l+r)>>;

    tree[z].nx[]=merge(tree[x].nx[],tree[y].nx[],l,mid);

    tree[z].nx[]=merge(tree[x].nx[],tree[y].nx[],mid+,r);

    update(z);

    return z;

}

int cnt[N*+],p[N*+];

void update()

{

    for(int i=;i<=top;i++)cnt[sam[i].step]++;

    for(int i=;i<=top;i++)cnt[i]+=cnt[i-];

    for(int i=top;i>=;i--)p[cnt[sam[i].step]--]=i;

    for(int i=top;i>=;i--)

        rt[sam[p[i]].pre]=merge(rt[sam[p[i]].pre],rt[p[i]],,m);

}

void deal()

{

    logg=log(top)/log();

    for(int i=;i<=top;i++)f[][i]=sam[i].pre;

    for(int j=;j<=logg;j++)

    for(int i=;i<=top;i++)

    f[j][i]=f[j-][f[j-][i]];

}

data query(int k,int l,int r,int L,int R)

{

    if(!k)return (data){,l};

    if(L==l&&R==r)return (data){tree[k].big,tree[k].pos};

    int mid=(L+R)>>;

    if(r<=mid)return query(tree[k].nx[],l,r,L,mid);

    else if(mid<l)return query(tree[k].nx[],l,r,mid+,R);

    else

    {

        data t1=query(tree[k].nx[],l,mid,L,mid),t2=query(tree[k].nx[],mid+,r,mid+,R);

        if(t1.x>t2.x||(t1.x==t2.x&&t1.y<t2.y))return t1;

        else return t2;

    }

}

void read(int &x)

{

    x=;char ch=getchar();

    while(ch<''||ch>'')ch=getchar();

    while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

}

int main()

{

    freopen("C.in","r",stdin);

    freopen("C2.out","w",stdout);

    scanf("%s",str);

    n=strlen(str);

    for(int i=;i<n;i++)extend(str[i]-'a'),pos[i+]=now;

    extend();

    scanf("%d",&m);

    for(int i=;i<=m;i++)

    {

        scanf("%s",str);leng=strlen(str);

        for(int j=;j<leng;j++)extend(str[j]-'a'),insert(rt[now],,m,i);

        extend();

    }

    deal();update();

    scanf("%d",&q);

    for(int i=;i<=q;i++)

    {

        scanf("%d%d%d%d",&l,&r,&pl,&pr);

        int x=find(pl,pr);data tmp;

        tmp=query(rt[x],l,r,,m);

        if(tmp.x==)tmp.y=l;

        printf("%d %d\n",tmp.y,tmp.x);

    }

    return ;

}

第二种写法：

将串连在一起求SA，设L为小于rank[pl]的第一个height[L]=pr-pl+1，R为大于rank[pl]的第一个height[R]=pr-pl+1。那么[pl,pr]能匹配的后缀区间即[L,R]。给后缀标记一下属于哪个特殊串，将题目变成了求区间众数。有趣的是这些区间不是包含关系就是相离关系。
令height[i]=(i-1,i)的（无向）边权，那么一次询问就是询问点rank[pl]只经过边权大于等于(pr-pl+1)的边所能到达点中出现次数最多的特殊串。
于是变成B3545Peaks加强版，用线段树维护，线段树合并实现。

O(nlogn)

#include<cstdio>

#include<cmath>

#include<cstring>

#include<vector>

const int limt(),len(),lem();

int tmp[len+],cnt[len+],p[len+];

int rank[len*+],sfa[len+],height[len+];

int str[len+],color[len+],val[len*+];

int n,m,Q,leng,l,r,pl,pr,x;char ch[len+];

struct Node{int nd,nx,co;}bot[len*+];int tot,first[len*+];

int g[][len*+],f[][len*+],logg;

int father[len*+],now,last;

std::vector<int>weight[len+];

struct ANS

{

    unsigned short int big,pos;

inline ANS operator +(const ANS&A)const{return (ANS){big+A.big,pos};}

inline ANS operator *(const ANS&A)const{if(A.big<big||(big==A.big&&pos<A.pos))return (ANS){big,pos};return A;}

}ans;

struct SegMent{int nx[];ANS key;}tree[lem+];int stot,root[len*+];

void read(int &x)

{

    x=;int f=;char ch=getchar();

    while((ch<''||ch>'')&&(ch!='-')){ch=getchar();}if(ch=='-')f=-,ch=getchar();

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    if(f<)x=-x;

}

void add(int a,int b,int c){bot[++tot]=(Node){b,first[a],c};first[a]=tot;}

void swap(int &a,int &b){if(a==b)return;a^=b;b^=a;a^=b;}

int min(int a,int b){return a>b?b:a;}

bool com(int x,int y,int l){return rank[x]==rank[y]&&rank[x+l]==rank[y+l];}

void doubling()

{

    for(int i=;i<=n;i++)rank[i]=str[i],sfa[i]=i;

    for(int pos=,l=,sigma=limt;pos<n;sigma=pos)

    {

        pos=;

        for(int i=n-l+;i<=n;i++)p[++pos]=i;

        for(int i=;i<=n;i++)if(sfa[i]>l)p[++pos]=sfa[i]-l;

        memset(cnt,,sizeof(int)*(sigma+));pos=;

        for(int i=;i<=n;i++)cnt[rank[i]]++;

        for(int i=;i<=sigma;i++)cnt[i]+=cnt[i-];

        for(int i=n;i>=;i--)sfa[cnt[rank[p[i]]]--]=p[i];

        for(int i=;i<=n;i++)tmp[sfa[i]]=com(sfa[i],sfa[i-],l)?pos:++pos;

        for(int i=;i<=n;i++)rank[i]=tmp[i];

        l=!l?:l<<;

    }

    for(int i=;i<=n;i++)rank[sfa[i]]=i;

    for(int i=,j,k;i<=n;i++)

    {

        k=sfa[rank[i]-]; if(!k)continue;

        j=height[rank[i-]]; if(j)j--;

        while(str[i+j]==str[k+j])

            j++;

        height[rank[i]]=j;

    }

}

int gf(int x)

{

    int v=x,o;while(v!=father[v])v=father[v];

    for(;x!=father[x];x=o){o=father[x];father[x]=v;}

    return v;

}

void exchange()

{

    for(int i=;i<=n;i++)weight[height[i]].push_back(i);

    for(int i=;i<=n;i++)val[i]=color[sfa[i]];

    for(int i=;i<=n*;i++)father[i]=i; now=n;last=now;

    for(int i=n,fa,fb;i>=;i--)

    {

        last=now;

        for(int v=;v<(int)weight[i].size();v++)

        {

            int t=weight[i][v];

            fa=gf(weight[i][v]-);fb=gf(weight[i][v]);

            if(fa!=fb)

            {

                now++;

                father[fb]=father[fa]=father[now];

                if(now!=fb)add(now,fb,i);

                if(now!=fa)add(now,fa,i);

            }

        }

    }

    now++;

    for(int i=,fa;i<=n;i++)

    {

        fa=gf(i);

        if(fa!=now)add(now,fa,);father[fa]=now;

    }

}

void update(int k){tree[k].key=tree[tree[k].nx[]].key*tree[tree[k].nx[]].key;}

void insert(int &k,int l,int r,int x)

{

    if(!k)k=++stot;

    if(l==r){tree[k].key.big++;tree[k].key.pos=l;return;}

    int mid=(l+r)>>;

    if(x<=mid)insert(tree[k].nx[],l,mid,x);

    else insert(tree[k].nx[],mid+,r,x);

    update(k);

}

int merge(int x,int y,int l,int r)

{

    if(!x||!y)return (x|y);

    int z=++stot,mid=(l+r)>>;

    if(l==r){tree[z].key=tree[x].key+tree[y].key;return z;}

    tree[z].nx[]=merge(tree[x].nx[],tree[y].nx[],l,mid);

    tree[z].nx[]=merge(tree[x].nx[],tree[y].nx[],mid+,r);

    update(z);

    return z;

}

void dfs(int x)

{

    if(val[x])insert(root[x],,m,val[x]);

    for(int v=first[x];v;v=bot[v].nx)

    {

        dfs(bot[v].nd); f[][bot[v].nd]=x; g[][bot[v].nd]=bot[v].co;

        root[x]=merge(root[x],root[bot[v].nd],,m);

//        fprintf(stdout,"%d\n",stot);

    }

}

void Fdeal()

{

    logg=log(now)/log();

    for(int j=;j<=logg;j++)

    for(int i=;i<=now;i++)

     f[j][i]=f[j-][f[j-][i]],g[j][i]=min(g[j-][i],g[j-][f[j-][i]]);

}

int find(int pl,int pr)

{

    int x=rank[pl];

    for(int j=logg;j>=;j--)

    if(g[j][x]>=pr-pl+)x=f[j][x];

    return x;

}

ANS query(int k,int L,int R,int l,int r)

{

    if(!k)return (ANS){,l};

    if(l==L&&r==R)return tree[k].key;

    int mid=(L+R)>>;

    if(r<=mid)return query(tree[k].nx[],L,mid,l,r);

    else if(mid<l)return query(tree[k].nx[],mid+,R,l,r);

    else return query(tree[k].nx[],L,mid,l,mid)*query(tree[k].nx[],mid+,R,mid+,r);

}

int main()

{

//    freopen("C.in","r",stdin);

//    freopen("C.out","w",stdout);

    scanf("%s",ch);

    leng=strlen(ch);

    for(int i=;i<leng;i++)str[++n]=ch[i]-'a'+;

    str[++n]=; scanf("%d",&m);

    for(int i=;i<=m;i++)

    {

        scanf("%s",ch);

        leng=strlen(ch);

        for(int j=;j<leng;j++)str[++n]=ch[j]-'a'+,color[n]=i;

        str[++n]=;

    }

    doubling();

    exchange();//将序列变成树

    dfs(now);

    Fdeal();

    scanf("%d",&Q);

    for(int i=;i<=Q;i++)

    {

        read(l);read(r);read(pl);read(pr);

        x=find(pl,pr);

        ans=query(root[x],,m,l,r);

        printf("%d %d\n",ans.pos,ans.big);

    }

    return ;

}

巴特西

Codeforces 666E Forensic Examination SAM or SA+线段树合并

E. Forensic Examination

最新文章

热门文章