题目链接
Description
给出\(n\)个序列。找出这\(n\)个序列的最长相同子串。
在这里，相同定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。
思路
参考：hzwer.
法一：kmp
在第一个串中枚举答案串的开头位置，与其余\(n-1\)个串做\(kmp\).
法二：后缀数组
将\(n\)个串拼接起来。二分答案\(len\)，将\(height\)分组，\(check\)是否有一组个数\(\geq len\)且落在\(n\)个不同的串中。
注意：\(n\)个串之间的\(n-1\)分隔符应该使用各不相同的符号。
对“相同”的处理
法一
kmp中，可重新定义“==”的含义。
思想类似 HDU 4749 & POJ 3167 kmp变形
法二：差分
Code
Ver. 1: kmp
#include <bits/stdc++.h>
#define maxn 1010
using namespace std;
typedef long long LL;
int a[maxn][maxn], f[maxn], m[maxn];
bool match(int* T, int* P, int p2, int p1) { return !p1 || T[p2]-T[p2-1]==P[p1]-P[p1-1]; }
void getfail(int* P, int n) {
f[0] = f[1] = 0;
for (int i = 1; i < n; ++i) {
int j = f[i];
while (j && !match(P, P, i, j)) j = f[j];
f[i+1] = match(P, P, i, j) ? j+1 : 0;
}
}
int kmp(int* T, int* P, int m, int n) {
int j = f[0], ret = 0;
for (int i = 0; i < m; ++i) {
while (j && !match(T, P, i, j)) j = f[j];
if (match(T, P, i, j)) ++j;
if (j==n) return n;
ret = max(ret, j);
}
return ret;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &m[i]);
for (int j = 0; j < m[i]; ++j) scanf("%d", &a[i][j]);
}
int ans = 0;
for (int i = 0; i < m[0]; ++i) {
int len = m[0]-i;
if (len < ans) break;
getfail(a[0]+i, len);
int minn = len;
for (int j = 1; j < n; ++j) minn = min(minn, kmp(a[j], a[0]+i, m[j], m[0]-i));
ans = max(ans, minn);
}
printf("%d\n", ans);
return 0;
}
Ver. 2: 后缀数组
#include <bits/stdc++.h>
#define maxn 1010
#define MAXN (int)1e7
using namespace std;
typedef long long LL;
int wa[MAXN], wb[MAXN], wv[MAXN], wt[MAXN], h[MAXN], rk[MAXN], sa[MAXN], n, r[MAXN],
id[MAXN], l[maxn], a[maxn][maxn], vis[maxn];
bool flag[MAXN];
vector<int> v;
bool cmp(int* r, int a, int b, int l) { return r[a] == r[b] && r[a+l] == r[b+l]; }
void init(int* r, int* sa, int n, int m) {
int* x=wa, *y=wb, *t, i, j, p;
for (i = 0; i < m; ++i) wt[i] = 0;
for (i = 0; i < n; ++i) ++wt[x[i] = r[i]];
for (i = 1; i < m; ++i) wt[i] += wt[i - 1];
for (i = n-1; i >= 0; --i) sa[--wt[x[i]]] = i;
for (j = 1, p = 1; p < n; j <<= 1, 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) wt[i] = 0;
for (i = 0; i < n; ++i) ++wt[wv[i]];
for (i = 1; i < m; ++i) wt[i] += wt[i - 1];
for (i = n-1; i >= 0; --i) sa[--wt[wv[i]]] = y[i];
t = x, x = y, y = t, x[sa[0]] = 0;
for (p = 1, i = 1; i < n; ++i) x[sa[i]] = cmp(y, sa[i], sa[i-1], j) ? p - 1 : p++;
}
for (i = 0; i < n; ++i) rk[sa[i]] = i;
int k = 0;
for (i = 0; i < n - 1; h[rk[i++]] = k) {
for (k = k ? --k : 0, j = sa[rk[i] - 1]; r[i+k] == r[j+k]; ++k);
}
}
int cur;
bool ok(vector<int>& v) {
++cur;
if (v.size()<n) return false;
int cnt = 0;
for (auto x : v) {
if (flag[x]) continue;
if (vis[id[x]]!=cur) ++cnt, vis[id[x]] = cur;
}
return cnt==n;
}
bool check(int len, int tot) {
bool cnt=0;
for (int i = 1; i < tot; ++i) {
if (h[i] < len) {
if (cnt && ok(v)) return true;
v.clear(); cnt = true;
}
v.push_back(sa[i]);
}
return false;
}
int main() {
int tot=0, m=0, x, le=1, ri=1010, ans=0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &l[i]); ri = min(ri, l[i]-1);
for (int j = 0; j < l[i]; ++j) {
scanf("%d", &a[i][j]);
if (j) m = max(m, a[i][j]-a[i][j-1]);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 1; j < l[i]; ++j) {
r[tot] = a[i][j]-a[i][j-1];
id[tot++] = i;
}
r[tot] = ++m; id[tot] = i; flag[tot++] = true;
}
r[tot-1] = 0;
int mn = r[0]; for (int i = 1; i < tot-1; ++i) mn = min(r[i], mn);
for (int i = 0; i < tot-1; ++i) r[i] -= mn-1; m -= mn-1;
init(r, sa, tot, ++m);
while (le <= ri) {
int mid = le+ri>>1;
if (check(mid, tot)) ans=mid, le=mid+1;
else ri=mid-1;
}
printf("%d\n", ans+1);
return 0;
}