【poj3294-不小于k个字符串中最长公共子串】后缀数组

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 using namespace std;
  6 
  7 const int N=102000;
  8 int n,cl,sl,ans,tt,c[N],tl[N],tr[N],al[N],ar[N],rk[N],Rs[N],sa[N],wr[N],y[N],h[N],st[N],ed[N];
  9 char s[1100];
 10 bool vis[1100];
 11 
 12 int minn(int x,int y){return x<y ? x:y;}
 13 
 14 
 15 void get_sa(int m)
 16 {
 17     for(int i=1;i<=cl;i++) rk[i]=c[i];
 18     for(int i=1;i<=m;i++) Rs[i]=0;
 19     for(int i=1;i<=cl;i++) Rs[rk[i]]++;
 20     for(int i=1;i<=m;i++) Rs[i]+=Rs[i-1];
 21     for(int i=cl;i>=1;i--) sa[Rs[rk[i]]--]=i;
 22     
 23     int ln=1,p=0;
 24     while(p<cl)
 25     {
 26         int k=0;
 27         for(int i=cl-ln+1;i<=cl;i++) y[++k]=i;
 28         for(int i=1;i<=cl;i++) if(sa[i]>ln) y[++k]=sa[i]-ln;
 29         
 30         for(int i=1;i<=cl;i++) wr[i]=rk[y[i]];
 31         for(int i=1;i<=m;i++) Rs[i]=0;
 32         for(int i=1;i<=cl;i++) Rs[wr[i]]++;
 33         for(int i=1;i<=m;i++) Rs[i]+=Rs[i-1];
 34         for(int i=cl;i>=1;i--) sa[Rs[wr[i]]--]=y[i];
 35         
 36         for(int i=1;i<=cl;i++) wr[i]=rk[i];
 37         for(int i=cl+1;i<=cl+ln;i++) wr[i]=0;
 38         p=1;rk[sa[1]]=1;
 39         for(int i=2;i<=cl;i++)
 40         {
 41             if(wr[sa[i]]!=wr[sa[i-1]] || wr[sa[i]+ln]!=wr[sa[i-1]+ln]) p++;
 42             rk[sa[i]]=p;
 43         }
 44         ln*=2,m=p;
 45     }
 46     sa[0]=0,rk[0]=0;
 47 }
 48 
 49 void get_h()
 50 {
 51     int k=0,j;
 52     for(int i=1;i<=cl;i++) if(rk[i]!=1)
 53     {
 54         j=sa[rk[i]-1];
 55         if(k) k--;
 56         while(c[j+k]==c[i+k] && j+k<=cl && i+k<=cl) k++;
 57         h[rk[i]]=k;
 58     }
 59     h[1]=0;
 60 }
 61 int idx(int x)
 62 {
 63     for(int i=1;i<=n;i++)
 64         if(st[i]<=x && x<=ed[i]) return i;
 65     return 0;
 66 }
 67 
 68 bool check(int k)
 69 {
 70     memset(vis,0,sizeof(vis));
 71     int now=cl;
 72     tt=0;
 73     for(int i=1;i<=cl;i++)
 74     {
 75         if(h[i]<k)
 76         {
 77             int cnt=0;
 78             for(int j=1;j<=n;j++) if(vis[j]) cnt++;
 79             if(cnt>(n/2)) tl[++tt]=sa[i-1],tr[tt]=tl[tt]+now-1; 
 80             memset(vis,0,sizeof(vis));
 81             now=cl-sa[i]+1;vis[idx(sa[i])]=1;
 82         }
 83         else
 84         {
 85             now=minn(now,h[i]);
 86             vis[idx(sa[i])]=1;
 87         }
 88     }
 89     int cnt=0;
 90     for(int j=1;j<=n;j++) if(vis[j]) cnt++;
 91     if(cnt>(n/2)) tl[++tt]=sa[cl-1],tr[tt]=tl[tt]+now-1; 
 92     if(tt) return 1;
 93     return 0;
 94 }
 95 
 96 int main()
 97 {
 98     freopen("a.in","r",stdin);
 99     int T=0;
100     while(1)
101     {
102         T++;
103         scanf("%d",&n);
104         if(n==0) return 0;
105         cl=0;ans=0;
106         for(int i=1;i<=n;i++)
107         {
108             scanf("%s",s+1);
109             sl=strlen(s+1);
110             if(i>1) c[++cl]=i;
111             st[i]=cl+1;
112             for(int j=1;j<=sl;j++) c[++cl]=s[j];
113             ed[i]=cl;
114         }
115         if(n==1) {printf("%c
",c[1]);continue;}
116         get_sa(200);
117         get_h();
118         // for(int i=1;i<=cl;i++) printf("%c",c[i]);printf("
");
119         // for(int i=1;i<=cl;i++) printf("%d ",sa[i]);printf("
");
120         // for(int i=1;i<=cl;i++) printf("%d ",rk[i]);printf("
");
121         // for(int i=1;i<=cl;i++) printf("%d ",h[i]);printf("
");
122         int l=0,r=cl,mid;
123         while(l<r)
124         {
125             mid=(l+r+1)/2;
126             if(check(mid)) 
127             {
128                 l=mid;
129                 ans=tt;
130                 for(int i=1;i<=tt;i++) al[i]=tl[i],ar[i]=tr[i];
131             }
132             else r=mid-1;
133         }
134         if(T>1) printf("
");
135         if(ans)
136         {
137             for(int i=1;i<=ans;i++)
138             {
139                 for(int j=al[i];j<=ar[i];j++) printf("%c",c[j]);
140                 printf("
");
141             }
142         }
143         else printf("?
");
144     }
145     return 0;
146 }