给出不超过5个字符串,求最长公共子串
总长度不超过1w
把几个串接到一起中间用不同的字符隔开
求出height之后,二分答案为k,在height数组中找到每一段连续的且均不小于k的数,用前缀和判断里面是否包含了来自每一个字符串的子串
$O(nlogn)$
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10000 + 10;
int n, m;
char s[maxn];
int sa[maxn], rank[maxn], height[maxn];
int tax[maxn], tp[maxn];
inline void tsort(){
for(int i = 1; i <= m; i++) tax[i] = 0;
for(int i = 1; i <= n; i++) tax[rank[i]]++;
for(int i = 2; i <= m; i++) tax[i] += tax[i - 1];
for(int i = n; i; i--) sa[tax[rank[tp[i]]]--] = tp[i];
}
inline bool cmp(int *arr, int l, int r, int k){
return arr[l] == arr[r] && arr[l + k] == arr[r + k];
}
void suffix_sort(){
m = 128;
for(int i = 1; i <= n; i++) tp[i] = i;
for(int i = 1; i <= n; i++) rank[i] = s[i];
tsort();
for(int k = 1, p = 0; p < n; k <<= 1, m = p){
p = k;
for(int i = 1; i <= k; i++) tp[i] = n - k + i;
for(int i = 1; i <= n; i++) if(sa[i] > k) tp[++p] = sa[i] - k;
tsort();
swap(rank, tp);
p = rank[sa[1]] = 1;
for(int i = 2; i <= n; i++)
rank[sa[i]] = cmp(tp, sa[i - 1], sa[i], k) ? p : ++p;
}
for(int i = 1, j, k = 0; i <= n; height[rank[i++]] = k)
for(k ? k-- : 0, j = sa[rank[i] - 1]; s[j + k] == s[i + k]; k++);
}
int L[10], R[10], sum[10][maxn] = {0};
char temp[] = {'!', '@', '#', '$', 0};
int q[maxn], qcnt;
int main(){
int N;
scanf("%d", &N);
n = 0;
for(int i = 0; i < N; i++){
L[i] = n + 1;
scanf("%s", s + 1 + n);
n += strlen(s + 1 + n);
R[i] = n;
s[++n] = temp[i];
}
s[n--] = 0;
suffix_sort();
for(int i = 0; i < N; i++){
for(int j = L[i]; j <= R[i]; j++)
sum[i][rank[j]]++;
for(int j = 1; j <= n; j++)
sum[i][j] += sum[i][j - 1];
}
int l = 1, r = maxn, mid, ans = 0;
for(int i = 0; i < N; i++) r = min(r, R[i] - L[i] + 1);
bool flag;
while(l <= r){
mid = l + r >> 1;
qcnt = 0;
for(int i = 1; i <= n; i++){
if(height[i] < mid) q[++qcnt] = i;
}
for(int i = 2; i <= qcnt; i++){
flag = true;
for(int j = 0; j < N; j++) flag &= sum[j][q[i] - 1] - sum[j][q[i - 1] - 1] > 0;
if(flag) break;
}
if(flag){
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
printf("%d\n", ans);
return 0;
}
知识兔