P2463

题目大意

定义两个数列相似表示：其中一个数列所有元素同时加上一个数能变成另一个数列。

现在给你 $N$ 个数列，求他们的最长相似子串。

解题思路

很显然可以先作差分，这样就把问题转换为了求 $N$ 个串的最长公共子序列。

这样就是一个字符串题了。我们发现字符集很大，所以考虑用 $SA$ 做。

我们先把所有的串拼接起来，中间加上不同的分割符。

然后进行后缀排序，此时又可以发现，只要在 $SA$ 上找到一个连续区间 $[l,r]$，使 $1\ldots N$ 在这个区间里都出现过，求 $\min_{l+1\le i\le r}h[i]$ 的最大值即可。

然后用双指针（尺取法）扫一遍就好了。

代码实现

/*
* @Author: ftt2333
* @Last Modified time: 2022-10-07 21:50:50
*/

#include <bits/stdc++.h>
using namespace std;
#define fin(s) freopen(s, "r", stdin)
#define fout(s) freopen(s, "w", stdout)
#define fio(s) fin(s".in"), fout(s".out")
using ll = long long; using ull = uint64_t;
using lll = __int128; using ulll = __uint128_t;
using db = double; using ldb = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vl = vector<ll>;
using uid = uniform_int_distribution<ll>;
using urd = uniform_real_distribution<db>;
#define rep(i, a, b) for(auto i = (a); i <= (b); i++)
#define per(i, a, b) for(auto i = (a); i >= (b); i--)
#define Edge(i, h, e, x) for(int i = h[x]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define All(a) (a).begin(), (a).end()
#define Size(a) ((int)(a).size())
#define mem(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))

mt19937 rnd(random_device{}());
const ll mod = 998244353;
const int N = 2e5 + 10;
int sa[N], tp[N], tax[N], rnk[N], n, m, h[N], a[N], col[N], cnt = 3728, t;
int tmp[N], num;

void sort() {
  fill(tax, tax + 1 + m, 0);
  rep(i, 1, n) tax[rnk[i]]++;
  rep(i, 1, m) tax[i] += tax[i - 1];
  per(i, n, 1) sa[tax[rnk[tp[i]]]--] = tp[i];
}
void suffixSort() {
  int tot; m = cnt;
  rep(i, 1, n) tp[i] = i, rnk[i] = a[i]; sort();
  for(int l = 1; tot < n; l <<= 1, m = tot) {
    tot = 0;
    rep(i, 1, l) tp[++tot] = n - l + i;
    rep(i, 1, n) if(sa[i] > l) tp[++tot] = sa[i] - l;
    sort(); swap(tp, rnk); rnk[sa[1]] = tot = 1;
    rep(i, 2, n)
      if(tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + l] == tp[sa[i - 1] + l]) rnk[sa[i]] = tot;
      else rnk[sa[i]] = ++tot;
  }
  rep(i, 1, n) rnk[sa[i]] = i;
  int k = 0;
  rep(i, 1, n) {
    if(rnk[i] == 1) continue;
    k -= !!k;
    int j = sa[rnk[i] - 1];
    for(; i + k <= n && j + k <= n && a[i + k] == a[j + k]; k++);
    h[rnk[i]] = k;
  }
}
void init() {
  cin >> t;
  rep(i, 1, t) {
    int k;
    cin >> k;
    int lst;
    cin >> lst;
    rep(j, 1, k - 1) {
      int x;
      cin >> x;
      a[++n] = x - lst + 1864;
      col[n] = i;
      lst = x;
    }
    a[++n] = ++cnt;
    col[n] = i;
  }
}
void solve() {
  deque<int> q;
  int r = 0;
  int ans = 0;
  rep(l, 1, n) {
    for(; r < n && num < t; ) {
      r++;
      for(; !q.empty() && h[q.back()] > h[r]; q.pop_back());
      q.push_back(r);
      tmp[col[sa[r]]]++;
      if(tmp[col[sa[r]]] == 1) num++;
    }
    for(; !q.empty() && q.front() < l + 1; ) q.pop_front();
    if(num == t && !q.empty()) ans = max(ans, h[q.front()]);
    tmp[col[sa[l]]]--;
    if(!tmp[col[sa[l]]]) num--;
  }
  cout << ans + 1 << '\n';
}

int main() {
  init();
  suffixSort();
  solve();
}