POJ 2774 后缀数组——最长公共子串

题意：

给定a串和b串，求他们的最长公共子串

分析：

把两个串连在一起。构造后缀数组。然后在构造等同于lcp(i-1,i)的height数组。

然后如果相邻的两个后缀分别属于a串和b串，那么就可以做答案。

时间复杂度O(nlgn)

1A

PS:第一次写后缀数组，写得有点繁杂，写多了，就会缩短了。。。

code:

#include #include #include #include #define N 300000
using namespace std;
char s[N],s1[N],s2[N];
struct gtp{int x,data[3],next;}g[N];
int n,len1,len2,sa[N],rank[N],a[N][3],e,ls[N],height[N];

void init(){
     scanf("%s",&s1);
     scanf("%s",&s2);
     len1=strlen(s1);
     len2=strlen(s2);
     n=0;
     for (int i=0;i         n++;
         s[n]=s1[i];
     }
     for (int i=0;i         n++;
         s[n]=s2[i];
     }
     s[0]=7;
}

void Sort(int l,int r){
     if (l>=r) return;
     int i=l,j=r;
     char mid=s[sa[(l+r)/2]];
     do{
          while (s[sa[i]]          while (s[sa[j]]>mid) j–;
          if (i<=j){
            swap(sa[i],sa[j]);
            i++; j–;
          }
     }while (i     Sort(l,j);
     Sort(i,r);
}

inline void add(int x,int data[]){
       e++;
       g[e].x=x;
       memcpy(g[e].data,data,sizeof(a[0]));
       g[e].next=ls[x];
       ls[x]=e;
}

void Jsort(){
     e=0;
     memset(ls,0,sizeof(int)*(n+2));
     for (int i=1;i<=n;i++)
       add(a[i][1],a[i]);
     int tail=0;
     for (int i=0;i<=n;i++){
         for (int t=ls[i];t!=0;t=g[t].next){
             tail++;
             memcpy(a[tail],g[t].data,sizeof(a[0]));
         }
     }

     e=0;
     memset(ls,0,sizeof(int)*(n+2));
     for (int i=n;i>=1;i–)
       add(a[i][0],a[i]);
     tail=0;
     for (int i=0;i<=n;i++)
       for (int t=ls[i];t!=0;t=g[t].next){
           tail++;
           memcpy(a[tail],g[t].data,sizeof(a[0]));
       }
}

inline bool flag(int d1[],int d2[]){
       if (d1[0]!=d2[0] || d1[1]!=d2[1]) return true;
       return false;
}

void buildarr(){
     for (int i=1;i<=n;i++) sa[i]=i;
     Sort(1,n);
     int t=0;
     for (int i=1;i<=n;i++){
       if (t==0 || s[sa[i]]!=s[sa[i-1]]) t++;
       rank[sa[i]]=t;
     }
     for (int i=1;1<         for (int j=1;j<=n;j++){
             a[j][0]=rank[j];
             if (j+(1<                          else a[j][1]=rank[j+(1<             a[j][2]=j;
         }
         Jsort();
         int t=0;
         for (int j=1;j<=n;j++){
             if (t==0 || flag(a[j],a[j-1])) t++;
             rank[a[j][2]]=t;
         }
     }
     for (int i=1;i<=n;i++) sa[rank[i]]=i;
}

void lcp(){
     memset(height,0,sizeof(height));
     for (int i=1;i<=n;i++){
         if (rank[i]==1) continue;
         int st,j,k;
         st=max(height[rank[i-1]]-1,0);
         j=i+st;
         k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && s[j]==s[k]){
               st++;
               j++;
               k++;
         }
         height[rank[i]]=st;
     }
}

inline bool part(int k){
            if (k<=len1) return true;
            return false;
       }

void print(){
     int ans=0;
     for (int i=2;i<=n;i++)
       if (part(sa[i-1])^part(sa[i])) ans=max(ans,height[i]);
     cout << ans << endl;
}

int main(){
    init();
    buildarr();
    lcp();
    print();
}