后缀数组

　　好感动，复习了下后缀数组居然写出来了……（感谢ykz大神）

　　求最长公共子串……WA了一发是因为：【不同字符串之间要用不同的特殊字符隔开】否则就会匹配到相同→_→比如都是aaa结尾，如果用相同特殊字符就会使得最长公共子串变成aaa#这样子……

 /**************************************************************

     Problem: 2946

     User: Tunix

     Language: C++

     Result: Accepted

     Time:60 ms

     Memory:4104 kb

 ****************************************************************/

 //BZOJ 2946

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 typedef long long LL;

 inline int getint(){

     int r=,v=; char ch=getchar();

     for(;!isdigit(ch);ch=getchar()) if(ch=='-')r=-;

     for(; isdigit(ch);ch=getchar()) v=v*+ch-'';

     return r*v;

 }

 const int N=1e5+,INF=~0u>>;

 /*******************template********************/

 int sa[N],rank[N],height[N],belong[N],wa[N],wb[N],c[N],n,m;

 int len[];

 char s[N];

 bool cmp(int *r,int a,int b,int l){

     return r[a]==r[b] && r[a+l]==r[b+l];

 }

 void DA(char *s,int *sa,int n,int m){

     int i,j,p,*x=wa,*y=wb;

     rep(i,m) c[i]=;

     rep(i,n) c[x[i]=s[i]]++;

     F(i,,m-) c[i]+=c[i-];

     D(i,n-,) sa[--c[x[i]]]=i;

     for(j=,p=;p<n;j<<=,m=p){

         for(p=,i=n-j;i<n;i++) y[p++]=i;

         rep(i,n) if (sa[i]>=j) y[p++]=sa[i]-j;

         rep(i,m) c[i]=;

         rep(i,n) c[x[y[i]]]++;

         F(i,,m-) c[i]+=c[i-];

         D(i,n-,) sa[--c[x[y[i]]]]=y[i];

         swap(x,y); p=; x[sa[]]=;

         F(i,,n-) x[sa[i]]=cmp(y,sa[i-],sa[i],j) ? p- : p++;

     }

 }

 void calheight(char *s,int *sa,int n){

     int k=;

     F(i,,n) rank[sa[i]]=i;

     rep(i,n){

         if (k) k--;

         int j=sa[rank[i]-];

         while(s[i+k]==s[j+k]) k++;

         height[rank[i]]=k;

     }

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("2946.in","r",stdin);

     freopen("2946.out","w",stdout);

 #endif

     n=getint();int l=;

     F(i,,n){

         scanf("%s",s+l);

         len[i]=strlen(s)-l;

         l=strlen(s);

         s[l++]='a'-n+i;

     }

     rep(i,l) s[i]=s[i]-'a'+;

     l--;

     DA(s,sa,l+,);

     calheight(s,sa,l);

     int tmp=;

     rep(i,l){

         if (s[i]<) {tmp++;continue;}

         belong[rank[i]]=tmp;

     }

     bool vis[]={};

     int L=,R=,mid,cnt,ans=;

     while(L<=R){

         mid=(L+R)>>;bool sign=;

         cnt=; memset(vis,,sizeof vis);

         F(i,n,l){

             if (height[i]<mid){

                 cnt=;memset(vis,,sizeof vis);

                 vis[belong[i]]=; continue;

             }

             if (!vis[belong[i]]) vis[belong[i]]=,cnt++;

             if (cnt==n) sign=;

         }

         if (sign) ans=mid,L=mid+;

         else R=mid-;

     }

     printf("%d\n",ans);

     return ;

 }

2946: [Poi2000]公共串

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 160 Solved: 67
[Submit][Status][Discuss]

Description

给出几个由小写字母构成的单词，求它们最长的公共子串的长度。

任务：

l 读入单词

l 计算最长公共子串的长度

l 输出结果

Input

文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。

Output

仅一行，一个整数，最长公共子串的长度。

Sample Input

3
abcb
bca
acbc

Sample Output

２

HINT

Source

[Submit][Status][Discuss]

公共

【BZOJ】【2946】【POI2000】公共串