https://vjudge.net/problem/UVA-11107
题意：
给定n个字符串，求出现在不小于n的一半个字符串的最长子串，如果有多个，则按字典序输出。
思路：
首先就是将这n个字符串连接起来，然后二分答案，每次只需要判断是否有一个长度为p的串在超过一半的串中连续出现，判断方法是扫描一遍height数组，把它分成若干段，每当height[i]小于p时开辟一个新段，则每一段的最初p个字符均相同。只要某一段中包含了超过n/2个原串的后缀，p就是满足条件的。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map> 10 #include<set> 11 using namespace std; 12 typedef long long ll; 13 typedef pair<int,int> pll; 14 const int INF = 0x3f3f3f3f; 15 const int maxn = 100000+1000; 16 17 int n,k; 18 int s[maxn]; 19 bool vis[120]; 20 int start[maxn]; 21 int belong[maxn]; 22 int sa[maxn],t[maxn],t2[maxn],c[maxn]; 23 int Rank[maxn],height[maxn]; 24 25 26 void build_sa(int m) 27 { 28 int *x=t,*y=t2; 29 //基数排序 30 for(int i=0;i<m;i++) c[i]=0; 31 for(int i=0;i<n;i++) c[x[i]=s[i]]++; 32 for(int i=1;i<m;i++) c[i]+=c[i-1]; 33 for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i; 34 for(int k=1;k<=n;k<<=1) 35 { 36 int p=0; 37 //直接利用sa数组排序第二关键字 38 for(int i=n-k;i<n;i++) y[p++]=i; 39 for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k; 40 //基数排序第一关键字 41 for(int i=0;i<m;i++) c[i]=0; 42 for(int i=0;i<n;i++) c[x[y[i]]]++; 43 for(int i=1;i<m;i++) c[i]+=c[i-1]; 44 for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i]; 45 //根据sa和y计算新的x数组 46 swap(x,y); 47 p=1; 48 x[sa[0]]=0; 49 for(int i=1;i<n;i++) 50 x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++; 51 if(p>=n) 52 break; 53 m=p; //下次基数排序的最大值 54 } 55 } 56 57 void getHeight(int n) 58 { 59 int i,j,k=0; 60 for(i=1;i<=n;i++) Rank[sa[i]]=i; 61 for(i=0;i<n;i++) 62 { 63 if(k) k--; 64 int j=sa[Rank[i]-1]; 65 while(s[i+k]==s[j+k]) k++; 66 height[Rank[i]]=k; 67 } 68 } 69 70 71 bool judge(int n, int len, int num) 72 { 73 int size=0; 74 int cnt = 0; 75 memset(vis,0,sizeof(vis)); 76 cnt++; 77 vis[belong[sa[0]]] = 1; 78 for(int i = 1;i < n;i++) 79 { 80 if(height[i] < len) 81 { 82 if(cnt>=num) start[++size]=sa[i-1]; //可行，保存好起点 83 memset(vis,0,sizeof(vis)); 84 vis[belong[sa[i]]] = 1; 85 cnt=1; 86 } 87 else 88 if(!vis[belong[sa[i]]]) 89 { 90 cnt++; 91 vis[belong[sa[i]]] = 1; 92 } 93 } 94 if(cnt>=num) start[++size]=sa[n-1]; //这儿需要注意，不要忽略了最后一段 95 if(size) 96 { 97 start[0]=size; 98 return 1; 99 } 100 return 0; 101 } 102 103 char str[1005]; 104 int main() 105 { 106 //freopen("in.txt","r",stdin); 107 bool flag=true; 108 while(~scanf("%d",&k) && k) 109 { 110 if(!flag) printf(" "); 111 else flag = false; 112 int pos=0,cas=1; 113 int l=0,r=0; 114 for(int i=1;i<=k;i++) 115 { 116 scanf("%s",str); 117 int len=strlen(str); 118 r=max(r,len); 119 for(int j=0;j<len;j++) 120 { 121 s[pos+j]=(int)str[j]+5; 122 belong[pos+j] = i; 123 } 124 s[pos+len]=cas++; 125 pos=pos+len+1; 126 } 127 s[pos]=0; 128 n=pos; 129 build_sa(150); 130 getHeight(n-1); 131 int ans=0; 132 while(l <= r) 133 { 134 int mid = (l+r) >> 1; 135 if(judge(pos,mid,k/2+1)) 136 { 137 ans = mid; 138 l = mid + 1; 139 } 140 else r = mid - 1; 141 } 142 if(ans == 0) printf("? "); 143 else 144 { 145 for(int i=1;i<=start[0];i++) 146 { 147 for(int j=start[i];j<start[i]+ans;j++) 148 printf("%c",s[j]-5); 149 printf(" "); 150 } 151 } 152 } 153 return 0; 154 }