某島

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

Luogu 2463. Sandy的卡片

同 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;
}