LCP+后缀数组 代码

2018-07-17 18:34:42


#include<bits/stdc++.h>
using namespace std;
int sa[100110],t[100110],t2[100110],c[100110],n,m,len;
int st[100],height[100110],rank[100110],ltt[100110][20];
string s,s1;

void clearc(){
    memset(sa,0,sizeof(sa));
    memset(t,0,sizeof(t));
    memset(t2,0,sizeof(t2));
    memset(c,0,sizeof(c));
    memset(st,0,sizeof(st));
}

void build(){
    int *x=t,*y=t2,m=0;
    memset(c,0,sizeof(c));
    for(int i=0;i<n;i++) c[x[i]=s[i]]++,m=max(m,x[i]);
    for(int i=0;i<m;i++) c[i]+=c[i-1];
    for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for(int k=1;k<=n;k<<=1){
        int p=0;
        for(int i=n-k;i<n;i++) y[p++]=i;
        for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k; 
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++) c[x[i]]++;
        for(int i=0;i<m;i++) c[i]+=c[i-1];
        for(int i=0;i<n;i++) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;
        x[sa[0]]=0;
        for(int i=1;i<n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k] ? p-1:p++);
        if(p>=n) return;
        m=p;
    }
}

void init(){
    for(int i=0;i<n;i++) ltt[i][0]=height[i];
    for(int l=1,k=1;k<n;l++,k<<=1)
        for(int i=0;i<n-k;i++)
            ltt[i][l]=min(ltt[i][l-1],ltt[i+k][l-1]);
}

void getheight(){
    int k=0;
    for(int i=0;i<n;i++) rank[sa[i]]=i;
    for(int i=0;i<n;i++){
        if(k) k--;
        int j=sa[rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        height[rank[i]]=k;
    }
}

int main(){
    while(cin>>n){
        if(n==0) break;
        clearc();
        s="";
        for(int i=1;i<=n;i++){
            cin>>s1;
            s+=s1+"$";
        }
        build();
        getheight();
        init();
    }
}