给出n个字符串，输出他们的最长公共子串，无解输出”IDENTITY LOST”
用不同的符号连接每个字符串，然后二分公共子串的长度，在$height$数组中看有没有连续$n$个$height$大于公共子串的长度，如果有，那么更新答案。
(此题暴力比SA快，而且poj上用SA一直TLE，Hdu上1840ms就过了)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "poj3450"
using namespace std;
const int MAXN = 200 + 5, MAXT = 4000 + 5;
char s[MAXT][MAXN];
int t, n, m, ans[MAXN], ll, mini;
int a[MAXT*MAXN+200], SA[MAXT*MAXN+200], rk[MAXT*MAXN+200], tp[MAXT*MAXN+200], tax[MAXT*MAXN+200], height[MAXT*MAXN+200], belong[MAXT*MAXN+200];
bool cmp(int *f, int i, int k) {return f[SA[i]]==f[SA[i-1]]&&f[SA[i]+k]==f[SA[i-1]+k];}
void build() {
for (int i=0;i<m;i++) tax[i] = 0;
for (int i=0;i<n;i++) tax[rk[i]=a[i]]++;
for (int i=1;i<m;i++) tax[i] += tax[i-1];
for (int i=n-1;i>=0;i--) SA[--tax[rk[i]]] = i;
int p;
for (int k=1;k<=n;k*=2) {
p = 0;
for (int i=n-k;i<n;i++) tp[p++] = i;
for (int i=0;i<n;i++) if (SA[i]>=k) tp[p++] = SA[i] - k;
for (int i=0;i<m;i++) tax[i] = 0;
for (int i=0;i<n;i++) tax[rk[tp[i]]]++;
for (int i=1;i<m;i++) tax[i] += tax[i-1];
for (int i=n-1;i>=0;i--) SA[--tax[rk[tp[i]]]] = tp[i];
swap(rk, tp), p = 0, rk[SA[0]] = 0;
for (int i=1;i<n;i++) rk[SA[i]] = cmp(tp, i, k) ? p : ++p;
if (++p>=n) break;
m = p;
}
}
void getH() {
int k = 0;
for (int i=0;i<n;i++) {
if (k) k--;
int j = SA[rk[i]-1];
while (a[i+k]==a[j+k]) k++;
height[rk[i]] = k;
}
}
void init() {
n = 0;
int orz = 200;
mini = 200000000;
for (int i=0;i<t;i++) {
scanf("%s", s[i]);
int l = strlen(s[i]); mini = min(mini, l);//取mini优化二分次数
for (int j=0;j<l;j++) belong[n] = i, a[n++] = s[i][j];
a[n] = orz;
a[n++] = orz++;
}
a[n-1] = 0;
m = orz + 5;
}
int used[MAXT];
bool check(int x) {
int tot = 0;
ms(used, false);
for (int i=2;i<n;i++) {
if (height[i]<x) {
tot = 0;
ms(used, false);
continue;
}
if (!used[belong[SA[i-1]]]) used[belong[SA[i-1]]] = true, ++tot;
if (!used[belong[SA[i]]]) used[belong[SA[i]]] = true, ++tot;
if (tot>=t) {
int k = 0;
for (int j=SA[i-1];j<SA[i-1]+height[i-1];j++) ans[k++] = a[j];
return true;
}
}
return false;
}
void solve() {
build(), getH();
int l = 0, r = mini+1; ll = 0;//左闭右开，要+1！
/* for (int i=0;i<n;i++) {
for (int j=SA[i];j<n;j++) printf("%4d ", a[j]);
putchar('\n');
}
return ;*/
while (l<r) {
int mid = (l+r)/2;
if (check(mid)) {
ll = mid;
l = mid + 1;
} else r = mid;
}
if (ll==0) printf("IDENTITY LOST\n");
else {
for (int i=0;i<ll;i++) printf("%c", ans[i]);
printf("\n");
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen(FN2".in","r",stdin);freopen("1.out","w",stdout);
#endif
while(scanf("%d", &t)==1&t) init(), solve();
return 0;
}
附上比SA快的暴力(可以对拍)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "poj3450"
using namespace std;
const int MAXN = 200 + 5, MAXT = 4000 + 5;
char s[MAXT][MAXN], ch[MAXN];
int t, n;
void init() {
for (int i=0;i<t;i++) {
scanf("%s", s[i]);
}
n = strlen(s[0]);
}
void solve() {
int ans = 0;
char fi[MAXN];
for (int bg=0;bg<n;bg++) {
for (int end=bg;end<n;end++) {
int k = 0;
int siz = end - bg + 1;
if (siz<ans) continue;
for (int i=0;i<n;i++) ch[i] = 0;
for (int i=bg;i<=end;i++) ch[k++] = s[0][i];
bool flag = false;
for (int i=1;i<t;i++) if (!strstr(s[i], ch)) {flag = true; break;}
if (!flag) {
if (siz==ans&&strcmp(ch, fi)>=0) continue;
memcpy(fi, ch, sizeof ch), ans = siz;
}
}
}
if (ans==0) printf("IDENTITY LOST\n");
else printf("%s\n", fi);
}
int main() {
#ifndef ONLINE_JUDGE
freopen(FN2".in","r",stdin);freopen("2.out","w",stdout);
#endif
while(scanf("%d", &t)==1&&t) init(), solve();
return 0;
}
