题目链接：http://poj.org/problem?id=3450
题意：给定n个字符串，求n个字符串的最长公共子串，无解输出IDENTITY LOST，否则最长的公共子串。有多组解时输出字典序最小的解
思路：后缀数组的解法，我们把n个串都链接起来，中间用一些互不相同的且都没在原串中出现过的字符来分割开。然后求后缀数组。由于求的是最长公共子串，所以我们可以二分长度x，于是问题就转变成了是否有一个长度为x的子串在n个字符串中都出现过。判断的方式是：以height数组进行分组，height值不小于x的为一组，如果有一组的后缀在原来n个串中都出现过。则说明存在长度为x的子串满足要求。由于答案要求输出字典序最小值的串，所以第一组满足要求的一定是字典序最小的解。因为sa数组的定义就是所有后缀按字典序排序。因此只需要找到第一组就可以返回了。
坑点：由于数据范围很大4000*200。所以在分组判断的时候不能情况所以的标记否则TLE到死。
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<time.h>
#include<cmath>
#include<set>
using namespace std;
typedef long long int LL;
const int MAXN = + ;
int wa[MAXN], wb[MAXN], wv[MAXN], WS[MAXN];
int cmp(int *r, int a, int b, int l)
{
return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int *r, int *sa, int n, int m)
{
int i, j, p, *x = wa, *y = wb, *t;
for (i = ; i < m; i++) WS[i] = ;
for (i = ; i < n; i++) WS[x[i] = r[i]]++;
for (i = ; i < m; i++) WS[i] += WS[i - ];
for (i = n - ; i >= ; i--) sa[--WS[x[i]]] = i;
for (j = , p = ; p < n; j *= , m = p)
{
for (p = , i = n - j; i < n; i++) y[p++] = i;
for (i = ; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = ; i < n; i++) wv[i] = x[y[i]];
for (i = ; i < m; i++) WS[i] = ;
for (i = ; i < n; i++) WS[wv[i]]++;
for (i = ; i < m; i++) WS[i] += WS[i - ];
for (i = n - ; i >= ; i--) sa[--WS[wv[i]]] = y[i];
for (t = x, x = y, y = t, p = , x[sa[]] = , i = ; i < n; i++)
x[sa[i]] = cmp(y, sa[i - ], sa[i], j) ? p - : p++;
}
return;
}
int Rank[MAXN], height[MAXN], sa[MAXN];
void calheight(int *r, int *sa, int n){
int i, j, k = ;
for (i = ; i <= n; i++) { Rank[sa[i]] = i; }
for (i = ; i < n; height[Rank[i++]] = k){
for (k ? k-- : , j = sa[Rank[i] - ]; r[i + k] == r[j + k]; k++);
}
return;
}
int r[MAXN], len, n, Index[MAXN], pos[ + ], vis[ + ];
char str[ + ];
bool check(int x){
int cnt = ;
for (int i = ; i <= n; i++){
vis[i] = ;//坑点，如果用memset来清空所以标记会TLE
}
for (int i = ; i < len; i++){
if (height[i] >= x){
if (!vis[Index[sa[i]]]){
cnt++;vis[Index[sa[i]]] = ;
}
if (!vis[Index[sa[i - ]]]){
cnt++;vis[Index[sa[i - ]]] = ;
}
if (cnt == n){
pos[x] = sa[i];return true;
}
}
else{
for (int i = ; i <= n; i++){
vis[i] = ;//坑点，如果用memset来清空所以标记会TLE
}
cnt = ;
}
}
return false;
}
void solve(){
int L = , R = , mid, ans = ;
memset(pos, , sizeof(ans));
while (R >= L){
mid = (L + R) / ;
if (check(mid)){
ans = mid;
L = mid + ;
}
else{
R = mid - ;
}
}
if (ans == ){
printf("IDENTITY LOST\n");
}
else{
for (int i = pos[ans], j = ; j < ans; j++, i++){
printf("%c", (r[i] - n - ) + 'a');
}
printf("\n");
}
}
int main(){
//#ifdef kirito
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//#endif
// int start = clock();
while (scanf("%d", &n) && n){
len = ;
for (int i = , val = ; i <= n; i++){
scanf("%s", &str);
for (int j = ; j < strlen(str); j++){
Index[len] = i; //属于哪个串
r[len++] = (str[j] - 'a' + n + ); //由于中间会添加n个分隔符。所以a字符映射成n+1
}
Index[len] = i;
r[len++] = val++;
}
da(r, sa, len, );
calheight(r, sa, len - );
solve();
}
//#ifdef LOCAL_TIME
// cout << "[Finished in " << clock() - start << " ms]" << endl;
//#endif
return ;
}
思路二：再来说说KMP的做法，由于求的是公共子串，所以答案[如果存在答案]肯定会在每个串中出现。子串一定是某个后缀的前缀，所以我们枚举随便一个串的所有后缀[这里我枚举的是第一个输入的串str[0]],然后我们对于每个后缀去匹配其他n-1个字符串，看看能匹配的最长前缀的长度是多少。比如现在有4个串，我们拿第一个串的某个后缀[后缀s]和其他3个串来匹配。s和str[1]匹配长度为3，说明后缀s的前3个字符在str[1]中连续出现过。s和str[2]匹配长度为2，说明后缀s的前2个字符在str[2]中连续出现过。s和str[3]匹配的长度是1，说明后缀s的前1个字符在str[3]中连续出现过。所以后缀s和str[1~3]的最长公共子串匹配的长度为1。然后考虑到字符串匹配的问题，所以对每个后缀都求一次next数组加速匹配即可。 在看到字典序的时候可以暴力判断，也可以求str[0]的名词数组rank来判断。而且本题KMP做法比后缀数组要快很多。
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<time.h>
#include<cmath>
#include<set>
using namespace std;
typedef long long int LL;
const int MAXN = + ;
const int MAXL = + ;
char str[MAXN][MAXL], ans[MAXL];
int Next[MAXL], n;
void getNext(char *str, int *Next, int len){
memset(Next, , sizeof(Next));
int i = , j = -; Next[] = -;
while (i < len){
if (j == - || str[i] == str[j]){
i++; j++; Next[i] = j;
}
else{
j = Next[j];
}
}
}
int LongestPre(char *s, int len){
getNext(s, Next, len);
int lenpre = MAXL;
for (int i = ; i < n; i++){ //与其他N-1个串进行匹配
int tmp = , k = ;
for (int j = ; j < strlen(str[i]); j++){
while (k != - && s[k] != str[i][j]){
k = Next[k];
}
if (k != - && s[k] == str[i][j]){
k++; tmp = max(tmp, k);
}
if (k == len){ break; }
if (k == -){ k = ; }
}
lenpre = min(lenpre, tmp); //匹配长度为所以长度的最小值
}
return lenpre;
}
int main(){
//#ifdef kirito
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//#endif
// int start = clock();
while (scanf("%d", &n) && n){
for (int i = ; i < n; i++){
scanf("%s", &str[i]);
}
int maxpre = , idx = , len = strlen(str[]);
for (int i = ; i < len; i++){//枚举str[0]的所以后缀
int lenpre = LongestPre(str[] + i, len - i);//后缀的最长前缀匹配长度
if (lenpre >= maxpre){
if (maxpre < lenpre){
maxpre = lenpre; idx = i;
}
else if (maxpre == lenpre){ //相同解，暴力判断字典序
for (int j = ; j < maxpre; j++){
if (str[][idx + j] > str[][i + j]){
idx = i; break;
}
if (str[][idx + j] < str[][i + j]){
break;
}
}
}
}
}
if (maxpre == ){
printf("IDENTITY LOST\n");
}
else{
for (int i = ; i < maxpre; i++){
printf("%c", str[][idx + i]);
}
printf("\n");
}
}
//#ifdef LOCAL_TIME
// cout << "[Finished in " << clock() - start << " ms]" << endl;
//#endif
return ;
}