此題就是給出N個字符串，然後求一個最長的子串，它至少出現在N/2+1個字符串中，
如果有多個這樣的子串，按字典序輸出，如果沒有這樣的子串，輸出?。
此題是羅穗骞論文裡面的例11，他有講述具體的解法。要用後綴數組做這樣的題真不
容易，用後綴數組就感覺是一件非常糾結的事情了。
這個題的解法還是那種模式化的思路。把N個字符串連接成一個，注意中間加不出現在
任何一個字符串中的分隔符，然後建立sa數組和height數組等。
最後二分答案，根據答案，即子串的長度對height數組進行分組，分組的思路還是羅穗
骞論文裡面例3的思路，即從到後枚舉height數組，把連續大於等於答案的值放做一組，
一旦小於答案那麼就是新的分組。這個題需要找到一些分組，其中的後綴是能夠出現在N個原
串中，這個分組的公共前綴就是sa[i]開始的nMid個字符了(nMid是二分時候獲得的子串長度)。
由於這個題需要按字典序輸出多個滿足要求的子串，所以麻煩了點。需要在Check函數裡面
記錄這些子串，而且輸出答案的時候需要排序，再unique，由於是按height數組的順序查找的，
而sa[i]已經排好序了，所以排序答案的過程可以省略，但是必須unique。想下Check函數裡面
遍歷height數組的過程就知道可能出現重復的子串。。。
代碼如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX_N = 110;
const int MAX_L = 1010;
const int MAX = MAX_N * MAX_L;
int nAns;
char szStr[MAX_L];
char szAns[MAX][MAX_L];
char* pszAns[MAX];
int nNum[MAX];
int nLoc[MAX];
bool bVis[MAX_N];
int sa[MAX], rank[MAX], height[MAX];
int wa[MAX], wb[MAX], wv[MAX], wd[MAX];
bool CmpStr(const char* pszOne, const char* pszTwo)
{
return strcmp(pszOne, pszTwo) < 0;
}
bool EqualStr(const char* pszOne, const char* pszTwo)
{
return strcmp(pszOne, pszTwo) == 0;
}
int cmp(int* r, int a, int b, int l)
{
return r[a] == r[b] && r[a + l] == r[b + l];
}
//倍增算法,r為待匹配數組,n為總長度,m為字符串范圍
void da(int* r, int n, int m)
{
int i, j, p, *x = wa, *y = wb;
for (i = 0; i < m; ++i) wd[i] = 0;
for (i = 0; i < n; ++i) wd[x[i] = r[i]]++;
for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
for (i = n - 1; i >= 0; --i) sa[--wd[x[i]]] = i;
for (j = 1, p = 1; p < n; j *= 2, m = p)
{
for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < n; ++i) wv[i] = x[y[i]];
for (i = 0; i < m; ++i) wd[i] = 0;
for (i = 0; i < n; ++i) wd[wv[i]]++;
for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
for (i = n - 1; i >= 0; --i) sa[--wd[wv[i]]] = y[i];
swap(x, y);
for (p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
{
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j)? p - 1 : p++;
}
}
}
//求height數組
void calHeight(int* r, 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)
{
if (k) --k;
for(j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++);
}
}
bool Check(int nMid, int nN, int nK)
{
int nCnt = 0;
int nNo = 0;
memset(bVis, false, sizeof(bVis));
for (int i = 1; i <= nN; ++i)
{
if (height[i] < nMid)
{
nCnt = 0;
memset(bVis, false, sizeof(bVis));
}
else
{
if (!bVis[nLoc[sa[i - 1]]])
{
++nCnt;
bVis[nLoc[sa[i - 1]]] = true;
}
if (!bVis[nLoc[sa[i]]])
{
++nCnt;
bVis[nLoc[sa[i]]] = true;
}
if (nCnt == nK)
{
for (int j = 0; j < nMid; ++j)
{
szAns[nNo][j] = nNum[sa[i] + j];
}
szAns[nNo][nMid] = 0;
++nNo;
nCnt = 0;
}
}
}
if (nNo > 0) nAns = nNo;
return nNo > 0;
}
int main()
{
int nN;
bool bFirst = true;
while (scanf("%d", &nN), nN)
{
if (bFirst) bFirst = false;
else putchar('\n');
int nEnd = 300;
int nP = 0;
for (int i = 0; i < nN; ++i)
{
scanf("%s", szStr);
int nLen = strlen(szStr);
for (int j = 0; j < nLen; ++j)
{
nNum[nP] = szStr[j];
nLoc[nP++] = i;
}
nNum[nP] = nEnd;
nLoc[nP++] = nEnd++;
}
nNum[nP] = 0;
if (nN == 1)
{
printf("%s\n\n", szStr);
continue;
}
da(nNum, nP + 1, 500);//500是估計的字符集大小
calHeight(nNum, nP);
int nLeft = 1, nRight = strlen(szStr);
int nTemp = 0, nMid;
int nK = nN / 2 + 1;
nAns = 0;
while (nLeft <= nRight)
{
nMid = (nLeft + nRight) >> 1;
if (Check(nMid, nP, nK))
{
nTemp = nMid;
nLeft = nMid + 1;
}
else nRight = nMid - 1;
}
if (nTemp == 0)
{
printf("?\n");
}
else
{
for (int i = 0; i < nAns; ++i)
{
pszAns[i] = szAns[i];
}
//sort(pszAns, pszAns + nAns, CmpStr);
nAns = unique(pszAns, pszAns + nAns, EqualStr) - pszAns;
for (int i = 0; i < nAns; ++i)
{
printf("%s\n", pszAns[i]);
}
}
}
return 0;
}
