本題練習後綴數組和LCP.二分查找長度是否滿足條件即可。
後綴數組模板：
[cpp]
int sa[Maxn],t[Maxn],t2[Maxn],c[Maxn];
int rank[Maxn],height[Maxn];
//傳遞的兩個參數：n是數組大小，m是數組內元素的Ascii碼的最大值+1
void build_sa(int n,int m)
{
int i,*x = t,*y = t2;
//基數排序
for(i=0; i<m; i++) c[i] = 0;
for(i=0; i<n; i++) c[x[i] = s[i]]++;
for(i=1; i<m; i++) c[i] += c[i-1];
for(i = n-1; i>=0; i--) sa[--c[x[i]]] = i;
for(int k=1; k<=n; k<<=1)
{
int p = 0;
//直接利用sa數組排序第二關鍵字
for(i = n-k; i<n; i++) y[p++] = i;
for(i = 0; i<n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
//基數排序第一關鍵字
for(i = 0; i < m; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[y[i]]]++;
for(i = 0; i < m; i++) c[i] += c[i-1];
for(i = n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i];
//根據sa 和y數組計算新的x數組
swap(x,y);
p = 1;
x[sa[0]] = 0;
for(i=1; i<n; i++)
{
x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1] + k] == y[sa[i] + k] ? p-1 : p++;
}
if(p >= n) break;
m = p;
}
}
//注意getHeight傳遞入的參數是原數組的長度-1.切記
void getHeight(int n)
{
int i, j, k = 0;
for(i = 1; i <= n; ++i) rank[sa[i]] = i;
for(i = 0; i < n; height[rank[i++]] = k)
for(k? k-- : 0, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; ++k);
return;
}
int sa[Maxn],t[Maxn],t2[Maxn],c[Maxn];
int rank[Maxn],height[Maxn];
//傳遞的兩個參數：n是數組大小，m是數組內元素的Ascii碼的最大值+1
void build_sa(int n,int m)
{
int i,*x = t,*y = t2;
//基數排序
for(i=0; i<m; i++) c[i] = 0;
for(i=0; i<n; i++) c[x[i] = s[i]]++;
for(i=1; i<m; i++) c[i] += c[i-1];
for(i = n-1; i>=0; i--) sa[--c[x[i]]] = i;
for(int k=1; k<=n; k<<=1)
{
int p = 0;
//直接利用sa數組排序第二關鍵字
for(i = n-k; i<n; i++) y[p++] = i;
for(i = 0; i<n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
//基數排序第一關鍵字
for(i = 0; i < m; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[y[i]]]++;
for(i = 0; i < m; i++) c[i] += c[i-1];
for(i = n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i];
//根據sa 和y數組計算新的x數組
swap(x,y);
p = 1;
x[sa[0]] = 0;
for(i=1; i<n; i++)
{
x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1] + k] == y[sa[i] + k] ? p-1 : p++;
}
if(p >= n) break;
m = p;
}
}
//注意getHeight傳遞入的參數是原數組的長度-1.切記
void getHeight(int n)
{
int i, j, k = 0;
for(i = 1; i <= n; ++i) rank[sa[i]] = i;
for(i = 0; i < n; height[rank[i++]] = k)
for(k? k-- : 0, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; ++k);
return;
}本題要注意兩點：getHeight(n)中傳遞的參數是數組長度-1，然後二分法的時候邊界要小心，n=1時，直接輸出原字符串即可。
[cpp]
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
#define Maxn 250000
#define Maxm 155
int s[Maxn];
int sa[Maxn],t[Maxn],t2[Maxn],c[Maxn];
int rank[Maxn],height[Maxn];
int tot;//整合後串的長度
//原串的個數
int n;
//整合後的新串中序號為i的字符歸屬的原串序號
int num[Maxn];
//當前段中含有的原串的後綴的個數
int flag[Maxm];
//最終解的後綴的序號（多組解不唯一）
int res[Maxn];
//最終解的個數
int ans_num;
void build_sa(int n,int m)
{
int i,*x = t,*y = t2;
//基數排序
for(i=0; i<m; i++) c[i] = 0;
for(i=0; i<n; i++) c[x[i] = s[i]]++;
for(i=1; i<m; i++) c[i] += c[i-1];
for(i = n-1; i>=0; i--) sa[--c[x[i]]] = i;
for(int k=1; k<=n; k<<=1)
{
int p = 0;
//直接利用sa數組排序第二關鍵字
for(i = n-k; i<n; i++) y[p++] = i;
for(i = 0; i<n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
//基數排序第一關鍵字
for(i = 0; i < m; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[y[i]]]++;
for(i = 0; i < m; i++) c[i] += c[i-1];
for(i = n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i];
//根據sa 和y數組計算新的x數組
swap(x,y);
p = 1;
x[sa[0]] = 0;
for(i=1; i<n; i++)
{
x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1] + k] == y[sa[i] + k] ? p-1 : p++;
}
if(p >= n) break;
m = p;
}
}
void getHeight(int n)
{
int i, j, k = 0;
for(i = 1; i <= n; ++i) rank[sa[i]] = i;
for(i = 0; i < n; height[rank[i++]] = k)
for(k? k-- : 0, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; ++k);
return;
}
bool possible(int L)
{
memset(flag,0,sizeof(flag));
int t = 0;//包含原串的個數
int lock = 0;
for(int i=1; i<tot; i++)
{
if(height[i] >= L)
{
flag[num[sa[i]]] = flag[num[sa[i-1]]] = 1;
}
else
{
for(int j=0; j<n; j++) if(flag[j]) t++;
if(t>n/2)
{
if(lock == 0)
{
ans_num = 0;
lock = 1;
}
res[ans_num++] = sa[i-1];
}
memset(flag,0,sizeof(flag));
t = 0;
}
}
//處理最後的段
t = 0;
for(int j=0; j<n; j++) if(flag[j]) t++;
if(t>n/2)
{
if(lock == 0)
{
ans_num = 0;
lock = 1;
}
res[ans_num++] = sa[n-1];
}
if(lock == 1) return true;
return false;
}
void binarySearch(int _l,int _r)
{
int l = _l,r = _r;
int mid;//最長的長度
int ans_len = l;
int lock = 0;
while(l < r)
{
mid = (l + r + 1)/2;
if(possible(mid))
{
lock = 1;
ans_len = mid;
l = mid;
}
else
{
r = mid - 1;
}
}
if(possible(ans_len)) lock = 1;
if(!lock)
{
puts("?");
return;
}
for(int i=0; i<ans_num; i++)
{
for(int j=res[i]; j<res[i] + ans_len; j++) printf("%c",s[j] - 1 + 'a');
puts("");
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int len;
int r = 0,l = 0;
char temp[1500];
int cas = 0;
while(scanf(" %d",&n)!=EOF && n!=0)
{
cas++;
if(cas!=1) puts("");
tot = 0;
l = 1;
r = 0;//最長的長度
for(int i=0; i<n; i++)
{
scanf(" %s",temp);
len = strlen(temp);
if(len > r) r = len;
for(int j=0; j<len; j++)
{
num[tot] = i;
s[tot++] = temp[j] - 'a' + 1;
}
s[tot++] = 26 + i + 1;
}
s[tot++] = 0;
if(n == 1)
{
printf("%s\n",temp);
continue;
}
build_sa(tot,26 + n + 1);
//注意傳遞的參數是長度-1
getHeight(tot-1);
binarySearch(l,r);
}
return 0;
}
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
#define Maxn 250000
#define Maxm 155
int s[Maxn];
int sa[Maxn],t[Maxn],t2[Maxn],c[Maxn];
int rank[Maxn],height[Maxn];
int tot;//整合後串的長度
//原串的個數
int n;
//整合後的新串中序號為i的字符歸屬的原串序號
int num[Maxn];
//當前段中含有的原串的後綴的個數
int flag[Maxm];
//最終解的後綴的序號（多組解不唯一）
int res[Maxn];
//最終解的個數
int ans_num;
void build_sa(int n,int m)
{
int i,*x = t,*y = t2;
//基數排序
for(i=0; i<m; i++) c[i] = 0;
for(i=0; i<n; i++) c[x[i] = s[i]]++;
for(i=1; i<m; i++) c[i] += c[i-1];
for(i = n-1; i>=0; i--) sa[--c[x[i]]] = i;
for(int k=1; k<=n; k<<=1)
{
int p = 0;
//直接利用sa數組排序第二關鍵字
for(i = n-k; i<n; i++) y[p++] = i;
for(i = 0; i<n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
//基數排序第一關鍵字
for(i = 0; i < m; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[y[i]]]++;
for(i = 0; i < m; i++) c[i] += c[i-1];
for(i = n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i];
//根據sa 和y數組計算新的x數組
swap(x,y);
p = 1;
x[sa[0]] = 0;
for(i=1; i<n; i++)
{
x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1] + k] == y[sa[i] + k] ? p-1 : p++;
}
if(p >= n) break;
m = p;
}
}
void getHeight(int n)
{
int i, j, k = 0;
for(i = 1; i <= n; ++i) rank[sa[i]] = i;
for(i = 0; i < n; height[rank[i++]] = k)
for(k? k-- : 0, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; ++k);
return;
}
bool possible(int L)
{
memset(flag,0,sizeof(flag));
int t = 0;//包含原串的個數
int lock = 0;
for(int i=1; i<tot; i++)
{
if(height[i] >= L)
{
flag[num[sa[i]]] = flag[num[sa[i-1]]] = 1;
}
else
{
for(int j=0; j<n; j++) if(flag[j]) t++;
if(t>n/2)
{
if(lock == 0)
{
ans_num = 0;
lock = 1;
}
res[ans_num++] = sa[i-1];
}
memset(flag,0,sizeof(flag));
t = 0;
}
}
//處理最後的段
t = 0;
for(int j=0; j<n; j++) if(flag[j]) t++;
if(t>n/2)
{
if(lock == 0)
{
ans_num = 0;
lock = 1;
}
res[ans_num++] = sa[n-1];
}
if(lock == 1) return true;
return false;
}
void binarySearch(int _l,int _r)
{
int l = _l,r = _r;
int mid;//最長的長度
int ans_len = l;
int lock = 0;
while(l < r)
{
mid = (l + r + 1)/2;
if(possible(mid))
{
lock = 1;
ans_len = mid;
l = mid;
}
else
{
r = mid - 1;
}
}
if(possible(ans_len)) lock = 1;
if(!lock)
{
puts("?");
return;
}
for(int i=0; i<ans_num; i++)
{
for(int j=res[i]; j<res[i] + ans_len; j++) printf("%c",s[j] - 1 + 'a');
puts("");
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int len;
int r = 0,l = 0;
char temp[1500];
int cas = 0;
while(scanf(" %d",&n)!=EOF && n!=0)
{
cas++;
if(cas!=1) puts("");
tot = 0;
l = 1;
r = 0;//最長的長度
for(int i=0; i<n; i++)
{
scanf(" %s",temp);
len = strlen(temp);
if(len > r) r = len;
for(int j=0; j<len; j++)
{
num[tot] = i;
s[tot++] = temp[j] - 'a' + 1;
}
s[tot++] = 26 + i + 1;
}
s[tot++] = 0;
if(n == 1)
{
printf("%s\n",temp);
continue;
}
build_sa(tot,26 + n + 1);
//注意傳遞的參數是長度-1
getHeight(tot-1);
binarySearch(l,r);
}
return 0;
}
