某岛

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

SPOJ AE5A2. Quasi-template


//}/* .................................................................................................................................. */
 
const int N = int(4e5) + 9, C = 26;
 
 
namespace Splay{
 
struct node{
 
    static node*NIL;node*c[2],*p;
    int ll,ky,rr,dd;
 
#define NIL node::NIL
#define l c[0]
#define r c[1]
#define lx x->l
#define rx x->r
 
    void reset(int v = 0){
        l = r = p = NIL;
        dd = 0, ll = rr = ky = v;
    }
 
    node(int v = 0){
        reset(v);
    }
 
    void upd(){
        dd = 0;
        if (l == NIL) ll = ky; else ll = l->ll, checkMax(dd, max(l->dd, ky-l->rr));
        if (r == NIL) rr = ky; else rr = r->rr, checkMax(dd, max(r->dd, r->ll-ky));;
    }
 
    void setc(int d, node *x){c[d]=x,x->p=this;}
    int sgn(){return p->r==this;}
 
    void rot(int d){
        node*y=p,*z=y->p; z->setc(y->sgn(), this);
        y->setc(d, c[!d]), setc(!d, y), y->upd();
    }
    void rot(){rot(sgn());}
 
    node *splay(){
        int a, b; while(p!=NIL){
            //cout << "!" << endl;
            if (p->p==NIL){rot();break;}
            else a=sgn(),b=p->sgn(),(a^b?this:p)->rot(a),rot(b);
        }
        upd();
        return this;
    }
 
    void insert(node *z){
        node *x=this,*y;  while (x != NIL){
            y = x, x = x->c[z->ky>x->ky];
        }
        y->setc(z->ky>y->ky, z);
        z->splay();
    }
 
} *NIL, *T[N];
 
node*merge(node *y, node *x){
    if(x == NIL) return y;
    y = merge(y, lx), y = merge(y, rx);
    lx = rx = NIL, y->insert(x);
    return x;
}
 
#undef l
#undef r
#undef lx
#undef rx
 
} using namespace Splay;
 
 
namespace KMP{
    void get_pi(const char P[], int n, int pi[]){
        for (int i = 2, j = pi[1] = 0; i <= n; ++i){
            while (j && P[i] != P[j+1]) j = pi[j];
            if (P[i] == P[j+1]) ++j;
            pi[i] = j;
        }
    }
} using namespace KMP;
 
 
namespace SAM{
 
    int trans[N][C], fail[N], len[N], cnt[N], tail, tot;
    char str[N/2]; int n, pi[N], ll[N], rr[N], dd[N], ml[N];
 
    inline int new_node(){
        RST(trans[tot]); cnt[tot] = 1; tail = tot;
        return tot++;
    }
 
    inline int new_node(int u){
        CPY(trans[tot], trans[u]); fail[tot] = fail[u], cnt[tot] = 0;
        return tot++;
    }
 
#define v trans[u]
#define f fail[u]
#define ff fail[uu]
 
    void 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;
            }
        }
    }
 
    void Init(){
        tot = 0, tail = new_node();
    }
 
    int Q[N], CC[N/2];
 
    void Topo(int*key){
        memset(CC, 0, sizeof(int)*(len[tail]+1));
        REP(i, tot) ++CC[key[i]];
        REP_1(i, len[tail]) CC[i] += CC[i-1];
        REP(i, tot) Q[--CC[key[i]]] = i;
    }
 
    void Run(){
 
        REP(u, tot) T[u] = cnt[u] ? new node(len[u]) : NIL;
 
        Topo(len);
 
        FOR(i, 1, tot){
            int u = Q[i];
            pi[u] = cnt[fail[u]] ? len[fail[u]] : pi[fail[u]];
        }
 
        DWN(i, tot, 1){
            int u = Q[i]; if (!cnt[u]) continue;
            ll[u] = T[u]->ll; rr[u] = T[u]->rr; dd[u] = T[u]->dd;
            T[f] = cnt[f] > cnt[u] ? merge(T[f], T[u]) : merge(T[u], T[f]);
            cnt[f] += cnt[u];
        }
 
        Topo(rr);
    }
 
//#undef v
//#undef f
//#undef ff
 
} using namespace SAM;
 
 
namespace Segment_Tree{
 
    const int NN = 4 * N;
 
#define lx (x<<1)
#define rx (lx|1)
#define ml (l + r >> 1)
#define mr (ml + 1)
#define lc lx, l, ml
#define rc rx, mr, r
#define root 1, 0, n-1
 
    int T[NN], M[NN], a, b, cur, ss, mm; VI adj[N/2];
 
    inline void Build(int x, int l, int r){
        T[x] = M[x] = 0; if (l < r) Build(lc), Build(rc);
    }
 
    inline void Insert(int x, int l, int r){
        ++T[x], checkMax(M[x], a); if (l == r) return;
        if (a < mr) Insert(lc); else Insert(rc);
    }
 
    inline void Query(int x, int l, int r){
        if (b < l || r < a) return;
        if (a <= l && r <= b) ss += T[x], checkMax(mm, M[x]);
        else Query(lc), Query(rc);
    }
 
    void Insert(int _a){
        a = _a; Insert(root);
    }
 
    void Query(int _a, int _b){
        a = _a, b = _b, ss = 0, mm = 0;
        Query(root);
    }
 
    void Move(int tar){
        while (cur <= tar){
            ECH(it, adj[cur]) Insert(*it);
            ++cur;
        }
    }
 
    void STInit(){
        //REP(i, n) CLR(adj[i]);
        //cur = 0;
    }
 
#undef ml
 
} using namespace Segment_Tree;
 
 
namespace SHash{
 
    uLL S[N], P[N];
    LL ans; int minLen;
 
    uLL h(int a, int b){
        return S[b]-S[a-1]*P[b-a+1];
    }
 
    void init(){
        P[0] = 1, S[0] = 0; REP_1(i, n) P[i] = P[i-1] * (C+1), S[i] = S[i-1] * (C+1) + (str[i]-'a'+1);
        ans = 0, minLen = n;
    }
 
    void jud(int &p1, int p2){
        int l = 0, r = minLen; while(l<r){
            int m = l+r>>1;
            if (h(p1,p1+m)==h(p2,p2+m)) l = m+1;
            else r = m;
        }
        if (str[p2+l]<str[p1+l]) p1 = p2;
    }
 
} using namespace SHash;
 
 
int main(){
 
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out2.txt", "w", stdout);
#endif
 
    NIL = new node(); NIL->reset();
 
    n = strlen(RS(str+1)); reverse(str+1, str+n+1); get_pi(str, n, pi); reverse(str+1, str+n+1);
    REP_1(i, n) adj[n-pi[i]].PB(n-i); Init(); REP_1(i, n) Ext(str[i]-'a'); Run();
 
    init(); FOR(i, 1, tot){
 
        int u = Q[i], L = max(ll[u]-pi[u],dd[u],len[f]+1), R=len[u]; if(L>R) continue;
 
        if(rr[u] == n){
            ans += R - L + 1, ml[u] = L;
        }
        else{
            Move(rr[u]); int l = rr[u]-R, r = rr[u]-L; Query(l, r); if (!ss) continue;
            ans += ss, ml[u] = rr[u] - mm;
        }
 
        checkMin(minLen, ml[u]);
    }
 
    OT(ans);
 
    int st, u; FOR_N(u, 1, tot) if (ml[u] == minLen){st = ll[u]-minLen+1; break;}
    FOR_N(u, u+1, tot) if (ml[u] == minLen) jud(st, ll[u]-minLen+1);
    FOR(i, st, st+minLen) putchar(str[i]); puts("");
}