# 某岛

… : "…アッカリ～ン . .. . " .. .
March 19, 2020

## Luogu 2463. Sandy的卡片

```
const int N = int(2e5) + 9;

namespace SAM{

map<int, int> trans[N]; int fail[N],len[N],tail,tot;

int new_node(){
trans[tot].clear();
}
int new_node(int u){
//trans[tot]=trans[u];
trans[tot].clear();
ECH(it, trans[u]) trans[tot][it->fi] = it->se;

fail[tot]=fail[u];
}
#define v trans[u]
#define f fail[u]
#define ff fail[uu]
int Ext(int c){
int u = tail, uu = new_node(); len[uu] = len[u] + 1;
while (u && !v) v = uu, u = f;
if (!u && !v) v = uu, ff = 0;
else{
if (len[v] == len[u] + 1) ff = v;
else{
int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
fail[_v] = ff = vv;
while (v == _v) v = vv, u = f;
}
}
return uu;
}
#define lenn C
int C[N], Q[N];
int a[N], n;

void get() {
RD(n); REP(i, n) RD(a[i]);
DWN(i, n-1, 0) a[i+1] -= a[i];
}

void Init(){
tot = 0; tail = new_node(); get(); REP(i, n) Ext(a[i]);
REP(i, tot) ++C[len[i]];
REP_1(i, len[tail]) C[i] += C[i-1];
REP(i, tot) Q[--C[len[i]]] = i;
}

void Run(){
fill(lenn, lenn+tot, 0); int u = 0, l = 0; get();
REP(i, n) {
int c = a[i];
while (u && !v) l = len[u = f];
if (u = v) checkMax(lenn[u], ++l);
}
DWN(i, tot, 1){
int u = Q[i]; checkMax(lenn[f], lenn[u]);
checkMin(len[u], lenn[u]);
}
}

} using namespace SAM;

int main(){
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
int n; RD(n); Init(); DO(n-1) Run();
int z = 0; REP(u, tot) checkMax(z, len[u]);
cout << z+1 << endl;
}
```