后缀数组

丧心病狂的集训队论文,不看了不看了

多篇同时食用

http://blog.csdn.net/wxfwxf328/article/details/7599929
http://www.cnblogs.com/shanchuan04/p/5324009.html
http://blog.csdn.net/yxuanwkeith/article/details/50636898
http://blog.csdn.net/xymscau/article/details/8798046
http://blog.csdn.net/say_c_box/article/details/77652568

总算A了的模板 //超容易写(抄)错 //SCU玄学卡空间
求最长公共子串,两个字符串连接处理

sa[1...n]:0...n-1 //排第sa[i]位的索引
he[1...n]:lcp(sa[i-1],sa[i])

#include<bits/stdc++.h>
#define rep(i,j,k) for((i)=(j);(i)<(k);(i)++)
#define rrep(i,j,k) for((i)=(j);(i)>=(k);(i)--)
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
#define rr register
using namespace std;
const int maxn = 2e6+11;
int wa[maxn],wb[maxn],wc[maxn],wd[maxn];
char str[maxn];int a[maxn];
int sa[maxn],ra[maxn],he[maxn];
int c0(int *r,int a,int b){
    return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}
int c12(int k,int *r,int a,int b){
    if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
    return r[a]<r[b]||r[a]==r[b]&&wc[a+1]<wc[b+1];
}
void sort(int *r,int *a,int *b,int n,int m){
    rr int i;
    rep(i,0,n) wc[i]=r[a[i]];
    rep(i,0,m) wd[i]=0;
    rep(i,0,n) wd[wc[i]]++;
    rep(i,1,m) wd[i]+=wd[i-1];
    rrep(i,n-1,0) b[--wd[wc[i]]]=a[i];
}
void dc3(int *r,int *sa,int n,int m){
    rr int i,j,p,ta=0,tb=(n+1)/3,tbc=0;
    int *rn=r+n,*san=sa+n;
    r[n]=r[n+1]=0;
    rep(i,0,n) if(i%3!=0) wa[tbc++]=i;
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
    p=1;rn[F(wb[0])]=0;
    rep(i,1,tbc) rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    if(p<tbc) dc3(rn,san,tbc,p);
    else rep(i,0,tbc) san[rn[i]]=i;
    rep(i,0,tbc) if(san[i]<tb) wb[ta++]=san[i]*3;
    if(n%3==1) wb[ta++]=n-1;
    sort(r,wb,wa,ta,m);
    rep(i,0,tbc) wc[wb[i]=G(san[i])]=i;
    for(i=j=p=0;i<ta&&j<tbc;p++) sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(;i<ta;p++) sa[p]=wa[i++];
    for(;j<tbc;p++) sa[p]=wb[j++];
}
void cal(int *r,int *sa,int n){
    rr int i,j,k=0;
    rep(i,1,n+1) ra[sa[i]]=i;
    for(i=0;i<n;he[ra[i++]]=k) for(k?k--:0,j=sa[ra[i]-1];r[i+k]==r[j+k];k++);
}
int main(){
    while(scanf("%s",str)!=EOF){
        int lena=strlen(str);
        scanf("%s",str+lena+1);
        int lenb=strlen(str+lena+1);
        int n=lena+lenb+1;
        rr int i,ans=0;
        for(i=0;i<n;i++) a[i]=str[i];a[lena]=1;a[n]=0;
        dc3(a,sa,n+1,200);//n+1
        cal(a,sa,n);//n
        for(i=1;i<n+1;i++){
            if(sa[i]<lena&&sa[i-1]<lena)continue;
            if(sa[i]>lena&&sa[i-1]>lena)continue;
            ans=max(ans,he[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

模板2 //不要乱动

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+11;
const int MAXN = 2e6+11;
#define rep(i,j,k) for((i)=(j);(i)<(k);(i)++)
#define rrep(i,j,k) for((i)=(j);(i)>=(k);(i)--)
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
#define rr register
#define dbg(n) rep(i,0,n+1){cout<<i<<" "<<sa[i]<<" "<<he[i]<<" "<<endl;if(str[sa[i]]=='A')cout<<"wwwwww\n";}
//sa[1...n]:0...n-1
//he[1...n]:lcp(sa[i-1],sa[i])
int wa[maxn],wb[maxn],wc[maxn],wd[MAXN];
int a[maxn];char str[maxn];
int sa[maxn],ra[maxn],he[maxn];
int c0(int *r,int a,int b){
    return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}
int c12(int k,int *r,int a,int b){
    if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
    return r[a]<r[b]||r[a]==r[b]&&wc[a+1]<wc[b+1];
}
void sort(int *r,int *a,int *b,int n,int m){
    rr int i;
    rep(i,0,n) wc[i]=r[a[i]];
    rep(i,0,m) wd[i]=0;
    rep(i,0,n) wd[wc[i]]++;
    rep(i,1,m) wd[i]+=wd[i-1];
    rrep(i,n-1,0) b[--wd[wc[i]]]=a[i];
}
void dc3(int *r,int *sa,int n,int m){
    rr int i,j,p,ta=0,tb=(n+1)/3,tbc=0;
    int *rn=r+n,*san=sa+n;
    r[n]=r[n+1]=0;
    rep(i,0,n) if(i%3!=0) wa[tbc++]=i;
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
    p=1;rn[F(wb[0])]=0;
    rep(i,1,tbc) rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    if(p<tbc) dc3(rn,san,tbc,p);
    else rep(i,0,tbc) san[rn[i]]=i;
    rep(i,0,tbc) if(san[i]<tb) wb[ta++]=san[i]*3;
    if(n%3==1) wb[ta++]=n-1;
    sort(r,wb,wa,ta,m);
    rep(i,0,tbc) wc[wb[i]=G(san[i])]=i;
    for(i=j=p=0;i<ta&&j<tbc;p++) sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(;i<ta;p++) sa[p]=wa[i++];
    for(;j<tbc;p++) sa[p]=wb[j++];
}
void cal(int *r,int *sa,int n){
    rr int i,j,k=0;
    rep(i,1,n+1) ra[sa[i]]=i;
    for(i=0;i<n;he[ra[i++]]=k) for(k?k--:0,j=sa[ra[i]-1];r[i+k]==r[j+k];k++);
}

struct RMQ{
    int rmq[maxn],mm[maxn],best[20][maxn];
    int i,j,a,b,t;
    void init(int n){
        rep(i,1,n+1) rmq[i]=he[i];
        mm[0]=-1;rep(i,1,n+1)mm[i]=(i&(i-1))==0?mm[i-1]+1:mm[i-1];
        rep(i,1,n+1) best[0][i]=i;
        rep(i,1,mm[n]+1) rep(j,1,n+1-(1<<i)+1){
            a=best[i-1][j];
            b=best[i-1][j+(1<<(i-1))];
            if(rmq[a]<rmq[b]) best[i][j]=a;
            else best[i][j]=b;
        }
    }
    int ask(int a,int b){
        t=mm[b-a+1];b-=(1<<t)-1;
        a=best[t][a];b=best[t][b];
        return rmq[a]<rmq[b]?a:b;
    }
}rmq;

int lcp(int a,int b){
    a=ra[a];b=ra[b];
    if(a>b)swap(a,b);
    return he[rmq.ask(a+1,b)];
}

POJ3216
求至少k次出现的最长匹配的长度

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 2e4+11;
const int MAXN = 1e6+11;
#define rep(i,j,k) for((i)=(j);(i)<(k);(i)++)
#define rrep(i,j,k) for((i)=(j);(i)>=(k);(i)--)
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
#define rr register

int wa[maxn],wb[maxn],wc[maxn],wd[MAXN];
int a[maxn];
int sa[maxn],ra[maxn],he[maxn];
int c0(int *r,int a,int b){
    return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}
int c12(int k,int *r,int a,int b){
    if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
    return r[a]<r[b]||r[a]==r[b]&&wc[a+1]<wc[b+1];
}
void sort(int *r,int *a,int *b,int n,int m){
    rr int i;
    rep(i,0,n) wc[i]=r[a[i]];
    rep(i,0,m) wd[i]=0;
    rep(i,0,n) wd[wc[i]]++;
    rep(i,1,m) wd[i]+=wd[i-1];
    rrep(i,n-1,0) b[--wd[wc[i]]]=a[i];
}
void dc3(int *r,int *sa,int n,int m){
    rr int i,j,p,ta=0,tb=(n+1)/3,tbc=0;
    int *rn=r+n,*san=sa+n;
    r[n]=r[n+1]=0;
    rep(i,0,n) if(i%3!=0) wa[tbc++]=i;
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
    p=1;rn[F(wb[0])]=0;
    rep(i,1,tbc) rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    if(p<tbc) dc3(rn,san,tbc,p);
    else rep(i,0,tbc) san[rn[i]]=i;
    rep(i,0,tbc) if(san[i]<tb) wb[ta++]=san[i]*3;
    if(n%3==1) wb[ta++]=n-1;
    sort(r,wb,wa,ta,m);
    rep(i,0,tbc) wc[wb[i]=G(san[i])]=i;
    for(i=j=p=0;i<ta&&j<tbc;p++) sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(;i<ta;p++) sa[p]=wa[i++];
    for(;j<tbc;p++) sa[p]=wb[j++];
}
void cal(int *r,int *sa,int n){
    rr int i,j,k=0;
    rep(i,1,n+1) ra[sa[i]]=i;
    for(i=0;i<n;he[ra[i++]]=k) for(k?k--:0,j=sa[ra[i]-1];r[i+k]==r[j+k];k++);
}
int k,n;
bool C(int mid){
    rr int i,s=1;
    rep(i,1,n+1){
        if(he[i]>=mid){
            s++;
            if(s>=k) return 1;
        }
        else s=1;
    }
    return 0;
}
int main(){
    while(scanf("%d%d",&n,&k)!=EOF){
        rr int i;rep(i,0,n){scanf("%d",&a[i]);a[i]++;}a[n]=0;
        dc3(a,sa,n+1,(int)1e6+11);cal(a,sa,n);
        int lx=1,rx=n,mid;
        while(lx<rx){
            mid=lx+(rx-lx+1)/2;
            if(C(mid)) lx=mid;
            else rx=mid-1;
        }
        printf("%d\n",lx);
    }
    return 0;
}

SPOJ DISUBSTR

rep(i,1,n+1) ans+=n-sa[i]-he[i];

错误的求最长回文串
如果直接正反相连两边找lcp,这个直接试很难找出错误,
若询问ABCDEFGHIDCBA则错了

//Wrong Answer
int main(){
    while(scanf("%s",str)!=EOF){
        rr int i,n=strlen(str);
        strcpy(trs,str);
        reverse(trs,trs+n);
        strcat(str+n+1,trs);str[n]=1;//cout<<str<<endl;
        rr int m=2*n+1;
        rep(i,0,m)a[i]=str[i];a[n]=1;a[m]=0;
        dc3(a,sa,m+1,233);cal(a,sa,m);
        rr int ans=0,pos=0;
        //dbg(m);
        rep(i,1,m+1){
            if(sa[i-1]<n&&sa[i]<n)continue;
            if(sa[i-1]>n&&sa[i]>n)continue;
            if(he[i]>ans) ans=he[i],pos=sa[i];
        }//cout<<ans<<endl;
        rep(i,0,n) if(ans==he[ra[i]]) {pos=i;break;} 
        rep(i,pos,pos+ans)printf("%c",str[i]);printf("\n");
        memset(str,0,sizeof str);memset(trs,0,sizeof trs);
    }
    return 0;
}

题外话:http://blog.sina.com.cn/s/blog_83e9c8da0100zo3k.html
http://blog.sina.com.cn/s/blog_83e9c8da0100z9e2.html
围观dalao:http://www.cnblogs.com/DragoonKiller/p/4338989.html

UPDATE!!

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e6+11;
const int oo = 0x3f3f3f3f;
const double eps = 1e-7;
typedef long long ll;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char str[maxn];
struct SA{
    int Rank[maxn],sa[maxn],tsa[maxn],A[maxn],B[maxn];
    int cntA[maxn],cntB[maxn];
    int height[maxn],best[maxn][30],n;//height[i]:第sa[i]与sa[i-1]的cp 
    void get(){
        n=strlen(str+1);
        rep(i,0,300) cntA[i]=0;
        rep(i,1,n) cntA[str[i]]++;
        rep(i,1,300) cntA[i]+=cntA[i-1];
        rrep(i,n,1) sa[cntA[str[i]]--]=i;
        Rank[sa[1]]=1;
        rep(i,2,n){
            if(str[sa[i]]==str[sa[i-1]]){
                Rank[sa[i]]=Rank[sa[i-1]];
            }else{
                Rank[sa[i]]=1+Rank[sa[i-1]];
            }
        }
        for(int l=1;Rank[sa[n]]<n;l<<=1){
            rep(i,1,n) cntA[i]=cntB[i]=0;
            rep(i,1,n) cntA[A[i]=Rank[i]]++;
            rep(i,1,n) cntB[B[i]=(i+l<=n?Rank[i+l]:0)]++;
            rep(i,1,n) cntA[i]+=cntA[i-1],cntB[i]+=cntB[i-1];
            rrep(i,n,1) tsa[cntB[B[i]]--]=i;
            rrep(i,n,1) sa[cntA[A[tsa[i]]]--]=tsa[i];
            Rank[sa[1]]=1;
            rep(i,2,n){
                bool flag=A[sa[i]]==A[sa[i-1]]&&B[sa[i]]==B[sa[i-1]];
                flag=!flag;
                Rank[sa[i]]=Rank[sa[i-1]]+flag;
            }
        }
    }
    void ht(){
        int j=0;
        rep(i,1,n){
            if(j) j--;
            while(str[i+j]==str[sa[Rank[i]-1]+j]) j++;
            height[Rank[i]]=j;
        }
    }
    void rmq(){
        rep(i,1,n) best[i][0]=height[i];
        for(int i=1;(1<<i)<=n;i++){
            for(int j=1;j+(1<<i)-1<=n;j++){
                best[j][i]=min(best[j][i],best[j+(1<<(i-1))][i-1]);
            }
        }
    }
    int query(int l,int r){
        if(l==r)return -oo;
        if(l>r)swap(l,r);
        l++;
        int k=log2(r-l+1);
        return min(best[l][k],best[r-(1<<k)+1][k]);
    }
}sa;
int main(){
    while(~s1(str)){
        sa.get();
        sa.ht();
        sa.rmq();
        int n=strlen(str+1);
        rep(i,1,n){
            cout<<sa.sa[i]<<" "<<sa.Rank[i]<<endl;
            cout<<"LCP"<<sa.query(i-1,i)<<endl;
        }
    }
}
#include<iostream>
#include<cstdio>
#include<cstring> 
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e6+11;
const int oo = 0x3f3f3f3f;
const double eps = 1e-7;
typedef long long ll;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char str[maxn];
struct SA{
    int Rank[maxn],sa[maxn],tsa[maxn],A[maxn],B[maxn];
    int cntA[maxn],cntB[maxn];
    int height[maxn],best[maxn][30],n;//height[i]:第sa[i]与sa[i-1]的cp 
    void get(){
        n=strlen(str+1);
        rep(i,0,300) cntA[i]=0;
        rep(i,1,n) cntA[str[i]]++;
        rep(i,1,300) cntA[i]+=cntA[i-1];
        rrep(i,n,1) sa[cntA[str[i]]--]=i;
        Rank[sa[1]]=1;
        rep(i,2,n){
            if(str[sa[i]]==str[sa[i-1]]){
                Rank[sa[i]]=Rank[sa[i-1]];
            }else{
                Rank[sa[i]]=1+Rank[sa[i-1]];
            }
        }
        for(int l=1;Rank[sa[n]]<n;l<<=1){
            rep(i,1,n) cntA[i]=cntB[i]=0;
            rep(i,1,n) cntA[A[i]=Rank[i]]++;
            rep(i,1,n) cntB[B[i]=(i+l<=n?Rank[i+l]:0)]++;
            rep(i,1,n) cntA[i]+=cntA[i-1],cntB[i]+=cntB[i-1];
            rrep(i,n,1) tsa[cntB[B[i]]--]=i;
            rrep(i,n,1) sa[cntA[A[tsa[i]]]--]=tsa[i];
            Rank[sa[1]]=1;
            rep(i,2,n){
                bool flag=A[sa[i]]==A[sa[i-1]]&&B[sa[i]]==B[sa[i-1]];
                flag=!flag;
                Rank[sa[i]]=Rank[sa[i-1]]+flag;
            }
        }
    }
    void ht(){
        int j=0;
        rep(i,1,n){
            if(j) j--;
            while(str[i+j]==str[sa[Rank[i]-1]+j]) j++;
            height[Rank[i]]=j;
        }
    }
    void rmq(){
        rep(i,1,n) best[i][0]=height[i];
        for(int i=1;(1<<i)<=n;i++){
            for(int j=1;j+(1<<i)-1<=n;j++){
                best[j][i]=min(best[j][i-1],best[j+(1<<(i-1))][i-1]);
            }
        }
    }
    int query(int l,int r){
        if(l==r)return -oo;
        if(l>r)swap(l,r);
        l++;
        int k=log2(r-l+1);
        return min(best[l][k],best[r-(1<<k)+1][k]);
    }
}sa;
char str1[maxn];
int main(){
    int T=read(); 
    while(T--){
        s1(str);
        int len=strlen(str+1);
        sa.get();
        sa.ht();
        sa.rmq(); 
        ll ans=0;
        rep(i,1,len){
            cout<<i<<" "<<sa.sa[i]<<" "<< str+sa.sa[i]<<endl;
            cout<<i<<" "<<sa.Rank[i]<<endl;
            cout<<i<<" "<<sa.height[i]<<endl; 
            cout<<i<<" "<<sa.query(i,i-1)<<endl; //sa[i] sa[i-1]的lcp ==height[i] 
        }
    }
    return 0;
}

标签: 算法, 学习

添加新评论