# 某島

… : "…アッカリ～ン . .. . " .. .
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;
}

inline int new_node(int u){
CPY(trans[tot], trans[u]); fail[tot] = fail[u], cnt[tot] = 0;
}

#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){
++cur;
}
}

void STInit(){
//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("");
}
```