[大除草术]后缀自动机构造后缀数组

终于弄出来了个版本……这个版本太,b……下次一定要改一改
不得不说这方法构造后缀树的方法还是挺好写的……
代码也不长……只是效率有点低,而且卖内存
效率低可能是因为我写疵了……下次想办法把reverse之类的stl去掉TAT

bzoj3238

虽然这题正常的做法是= =构造出后缀树,然后直接dfs就可以了……
但是毕竟我对后缀树的理解不深……所以我构造出了后缀数组然后乱搞
因为这题n=500000,后缀数组用倍增还是dc3都会tle(mato语)
所以我们上后缀自动机构造后缀树然后dfs出后缀数组!

bzoj_3238.cpp
#include<cstdio>
//妈妈我终于会写后缀树了!

#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 1500000
struct node{
    node*go[27],*pa;
    node*trans[27];
    int l,stpos,r;
}T[N],*stp=T,*root,*last,*samid[N];
int n,sa[N],height[N],rank[N],cnt;char st[N];
void expand(int x)
{
    node*p=stp++,*t=last;
    p->l=last->l+1;
    p->stpos=last->stpos+1;
    samid[p->stpos]=p;
    last=p;
    for(;t&&!t->go[x];t=t->pa)t->go[x]=p;
    if(!t)p->pa=root;
    else{
        if(t->l+1==t->go[x]->l)p->pa=t->go[x];
        else{
            node*r=stp++,*q=t->go[x];
            *r=*q;
            r->l=t->l+1;
            r->stpos=-1;
            q->pa=p->pa=r;
            for(;t&&t->go[x]==q;t=t->pa)t->go[x]=r;
        }
    }
}void build_suffixtree()
{
    for(int i=n;i>=1;i--)
    {
        for(node*x=samid[i];x&&!x->r;x=x->pa)x->r=i-1;
    }
    for(node *x=--stp;x>root;x--)
    {
        node*fa=x->pa;
        fa->trans[st[x->r-fa->l]-'a']=x;
    }
}void dfs(node*x)
{
    if(x->stpos>=1)sa[cnt++]=x->stpos-1;
    for(int i=0;i<26;i++)
        if(x->trans[i])dfs(x->trans[i]);
}int q[N],head,tail,Left[N],Right[N];
int main(){
    gets(st);root=stp++;last=root;
    n=strlen(st);
    for(int i=n-1;i>=0;i--)
        expand(st[i]-'a');
    reverse(st,st+n);
    build_suffixtree();
    dfs(root)
    reverse(st,st+n);
    for(int i=0;i<n;i++)sa[i]=n-sa[i]-1;
    for(int i=0;i<n;i++)rank[sa[i]]=i;
  //get a suffix array !

    for(int i=0,j=0;i<n;i++)
    {
        if(j)j--;
        if(rank[i]==n-1)continue;
        int p=sa[rank[i]+1];
        while(p+j<n&&i+j<n&&st[i+j]==st[p+j])
            j++;
        height[rank[i]]=j;
    }long long ans=(long long)(n+1)*n*(n-1)/2LL;
    head=0;q[tail++]=0;
    for(int i=1;i<n-1;i++)
    {
        while(head<tail&&height[q[tail-1]]>height[i])tail--;
        if(head<tail)Left[i]=q[tail-1]+1;
        else Left[i]=0;
        q[tail++]=i;
    }q[tail=0]=n-2;tail++;Right[n-2]=n-2;
    for(int i=n-3;i>=0;i--)
    {
        while(head<tail&&height[q[tail-1]]>=height[i])tail--;
        if(head<tail)Right[i]=q[tail-1]-1;
        else Right[i]=n-2;
        q[tail++]=i;
    }for(int i=0;i<n-1;i++)
    {
        ans-=(long long)(i-Left[i]+1)*(Right[i]-i+1)*2LL*height[i];
    }cout<<ans<<endl;
}

还有一个练手题……

poj2774

就是求两个字符串的LCS囧……
虽然这题后缀自动机可以直接搞……但是为了测试我的sam->sa我就写了这题……
非常搞笑的是这里我的倍增构sa比sam构sa快……可能是因为n太小了……

poj2774.cpp
#include<cstdio>
//妈妈我终于会写后缀树了!

#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 1500000
struct node{
    node*go[27],*pa;
    node*trans[27];
    int l,stpos,r;
}T[N],*stp=T,*root,*last,*samid[N];
int n,sa[N],height[N],rank[N],cnt;char st[N];
void expand(int x)
{
    node*p=stp++,*t=last;
    p->l=last->l+1;
    p->stpos=last->stpos+1;
    samid[p->stpos]=p;
    last=p;
    for(;t&&!t->go[x];t=t->pa)t->go[x]=p;
    if(!t)p->pa=root;
    else{
        if(t->l+1==t->go[x]->l)p->pa=t->go[x];
        else{
            node*r=stp++,*q=t->go[x];
            *r=*q;
            r->l=t->l+1;
            r->stpos=-1;
            q->pa=p->pa=r;
            for(;t&&t->go[x]==q;t=t->pa)t->go[x]=r;
        }
    }
}void build_suffixtree()
{
    for(int i=n;i>=1;i--)
    {
        for(node*x=samid[i];x&&!x->r;x=x->pa)x->r=i-1;
    }
    for(node *x=--stp;x>root;x--)
    {
        node*fa=x->pa;
        fa->trans[st[x->r-fa->l]-'a'+1]=x;
    }
}void dfs(node*x)
{
    if(x->stpos>=1&&x->stpos!=n)sa[cnt++]=x->stpos-1;
    for(int i=0;i<27;i++)
        if(x->trans[i])dfs(x->trans[i]);
}

int main(){
    gets(st+1);root=stp++;last=root;
    st[0]='a'-1;int pos=n=strlen(st);n++;st[pos]='a'-1;
    gets(st+n);n=strlen(st);
    for(int i=n-1;i>=0;i--)
        expand(st[i]-'a'+1);
    reverse(st,st+n);
    build_suffixtree();
    dfs(root);
    reverse(st,st+n);
    n--;pos--;
    for(int i=0;i<n;i++)st[i]=st[i+1];st[n]=0;
    for(int i=0;i<n;i++)sa[i]=n-sa[i]-1;
    for(int i=0;i<n;i++)rank[sa[i]]=i;
    for(int i=0,j=0;i<n;i++)
    {
        if(j)j--;
        if(rank[i]==n-1)continue;
        int p=sa[rank[i]+1];
        while(p+j<n&&i+j<n&&st[i+j]==st[p+j])
            j++;
        height[rank[i]]=j;
    }int ans=0;
    for(int i=0;i<n-1;i++)
    {
        int x=sa[i],y=sa[i+1];
        if(x>y)swap(x,y);
        if(x<pos&&y>pos)ans=max(height[i],ans);
    }printf("%d\n",ans);
}

Comments

comments powered by Disqus