【BZOJ3145】[Feyat cup 1.5]Str

2016.03.23 16:24 Wed | 48次阅读 | 旧日oi | 固定链接 | 源码

题解

后缀数组+并查集+启发式合并

我们把两个串放在一起跑一遍后缀数组,再把反串放到一起再跑一次后缀数组。
这样就可以得到每个位置往前往后和另一个串最长能匹配到哪。
然后,我们对向后匹配的那个后缀数组进行启发式合并。
对于每个元素,开两个set,存和这个点同一集合的点的下标-2在反串的后缀数组中的rank。
然后每次并查集可以合并两个set,合并的时候在两个set里分别求一下前驱后继,再求一下lcp就可以了。
复杂度是nlog^2n
upd:要特别注意第一个点和最后一个点不一样的时候的情况,还有,答案至少是1……

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 400005
struct Suffix_Array
{
    int s[N],sa[N],rk[N],SA[N],RK[N],v[N],h[N],len;
    int mn[N][19],lg[N];
    void mul(int k,int *sa,int *rk,int *SA,int *RK)
    {
        for(int i=1;i<=len;i++) v[rk[sa[i]]]=i;
        for(int i=len;i;i--) if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k;
        for(int i=len-k+1;i<=len;i++) SA[v[rk[i]]--]=i;
        for(int i=1;i<=len;i++) 
            RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i-1]+k]!=rk[SA[i]+k]);
    }
    void get_sa(int lim)
    {
        for(int i=1;i<=len;i++) v[s[i]]++;
        for(int i=1;i<=lim;i++) v[i]+=v[i-1];
        for(int i=1;i<=len;i++) sa[v[s[i]]--]=i;
        for(int i=1;i<=len;i++) rk[sa[i]]=rk[sa[i-1]]+(s[sa[i-1]]!=s[sa[i]]);
        for(int k=1;k<=len;k<<=1) 
        {
            mul(k,sa,rk,SA,RK);;
            memcpy(sa,SA,len+1<<2);
            memcpy(rk,RK,len+1<<2);
        }
        for(int k=0,j,i=1;i<=len;i++)
        {
            j=sa[rk[i]-1];
            while(s[j+k]==s[i+k]) k++;
            h[rk[i]]=k;if(k) k--;
        }
        for(int i=1;i<=len;i++) mn[i][0]=h[i];
        for(int j=1;(1<<j)<=len;j++) 
        {
            for(int i=1;i+(1<<j)-1<=len;i++)
                mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
        }
        for(int i=2;i<=len;i++) lg[i]=lg[i>>1]+1;
    }
    int get_mn(int l,int r)
    {
        int t=lg[r-l+1];
        return min(mn[l][t],mn[r-(1<<t)+1][t]);
    }
    int lcp(int x,int y)
    {
        if(x>y) swap(x,y);
        return get_mn(x+1,y);
    }
}a,b;
int n,m,ans;
char s1[N],s2[N];
int id[N],fa[N],siz[N];
bool cmp(int x,int y){return a.h[x]>a.h[y];}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
set<int> v1[N],v2[N];
set<int>::iterator it,tl,tr;
void merge(int x,int y,int len)
{
    x=find(x);y=find(y);
    if(siz[x]<siz[y]) swap(x,y);
    for(it=v1[y].begin();it!=v1[y].end();it++)
    {
        tl=tr=v2[x].lower_bound(*it);
        if(tr!=v2[x].end()) ans=max(ans,b.lcp(*it,*tr)+len+1);
        if(tl!=v2[x].begin()) ans=max(ans,b.lcp(*it,*--tl)+len+1);
    }
    for(it=v2[y].begin();it!=v2[y].end();it++)
    {
        tl=tr=v1[x].lower_bound(*it);
        if(tr!=v1[x].end()) ans=max(ans,b.lcp(*it,*tr)+len+1);
        if(tl!=v1[x].begin()) ans=max(ans,b.lcp(*it,*--tl)+len+1);
    }
    for(it=v1[y].begin();it!=v1[y].end();it++) v1[x].insert(*it);
    for(it=v2[y].begin();it!=v2[y].end();it++) v2[x].insert(*it);
    v1[y].clear();v2[y].clear();fa[y]=x;siz[x]+=siz[y];
}
int main()
{
    scanf("%s%s",s1+1,s2+1);n=strlen(s1+1);m=strlen(s2+1);
    for(int i=1;i<=n;i++) a.s[++a.len]=s1[i]-'a'+1;
    a.s[++a.len]=27;
    for(int i=1;i<=m;i++) a.s[++a.len]=s2[i]-'a'+1;
    for(int i=n;i;i--) b.s[++b.len]=s1[i]-'a'+1;
    b.s[++b.len]=27;
    for(int i=m;i;i--) b.s[++b.len]=s2[i]-'a'+1;
    a.get_sa(27);b.get_sa(27);
    for(int i=2;i<=a.len;i++) id[i]=i;
    sort(id+2,id+a.len+1,cmp);
    for(int i=1;i<=a.len;i++) 
    if((a.sa[i-1]<=n&&a.sa[i]>n+1)||(a.sa[i]<=n&&a.sa[i-1]>n+1))
        ans=max(ans,a.h[i]);
    for(int i=1;i<=a.len;i++) fa[i]=i,siz[i]=1;
    for(int i=1;i<=a.len;i++) 
    {
        if(a.sa[i]>2&&a.sa[i]<=n) v1[i].insert(b.rk[n+1-(a.sa[i]-2)]);
        if(a.sa[i]>n+3&&a.sa[i]<=n+m+1) v2[i].insert(b.rk[n+m+2-(a.sa[i]-2-n-1)]);
    }
    for(int i=2;i<=n;i++) ans=max(ans,a.lcp(a.rk[i],a.rk[n+3])+1);
    for(int i=2;i<=n;i++) ans=max(ans,b.lcp(b.rk[i],b.rk[n+3])+1);
    for(int i=2;i<=m;i++) ans=max(ans,a.lcp(a.rk[2],a.rk[n+i+1])+1);
    for(int i=2;i<=m;i++) ans=max(ans,b.lcp(b.rk[2],b.rk[n+i+1])+1);
    for(int i=2;i<=a.len;i++) merge(id[i]-1,id[i],a.h[id[i]]);
    printf("%d\n",max(ans,1));
}