同 SPOJ-LCS2，多串 lcs。

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(); return tot++; } 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]; return tot++; } #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; }