1.注意每两个串之间的连接符要不一样。

2.分组的时候要注意最后一组啊！又漏了！

3.开数组要考虑连接符的数量。100010是不够的至少要101000。

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           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
         
          =1;i--) sa[Rs[rk[i]]--]=i; 22      23     int ln=1,p=0; 24     while(p
          
           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]
           
            (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\n",c[1]);continue;}116 get_sa(200);117 get_h();118 // for(int i=1;i<=cl;i++) printf("%c",c[i]);printf("\n");119 // for(int i=1;i<=cl;i++) printf("%d ",sa[i]);printf("\n");120 // for(int i=1;i<=cl;i++) printf("%d ",rk[i]);printf("\n");121 // for(int i=1;i<=cl;i++) printf("%d ",h[i]);printf("\n");122 int l=0,r=cl,mid;123 while(l
            
             1) printf("\n");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("\n");141 }142 }143 else printf("?\n");144 }145 return 0;146 }