zkx06111's Blog

Suffix Automaton

| Comments

SPOJ NSUBSTR
SPOJ LCS
BZOJ 4516

LCS.cpp
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <algorithm>
#define REP(i, a, b) for (int i = a; i <= b; ++i)
#define PER(i, a, b) for (int i = a; i >= b; --i)
#define RVC(i, S) for (int i = 0; i < S.size(); ++i)
#define RAL(i, x) for (int i = fr[x]; i != -1; i = e[i].nxt)
#define ME I_love_CC
using namespace std;

inline int read(){
    int x = 0, f = 1, ch = getchar();
    while (ch < '0' || ch > '9'){if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

const int N = 250005;

struct State{
    State*par, *go[26];
    int val;
    State(): par(0), val(0){
        memset(go, 0, sizeof go);
    }
}statePool[N * 2], *root, *last, *cur;

void init(){
    cur = statePool;
    root = last = cur++;
}

State*newState(int _val){
    cur->val = _val;
    return cur++;
}

void extend(int w){
    State*p = last;
    State*np = newState(p->val + 1);
    while (p && p->go[w] == 0)
            p->go[w] = np, p = p->par;
    if (p == 0) np -> par = root;
    else{
        State*q = p->go[w];
        if (p->val + 1 == q->val)
            np->par = q;
        else{
            State*nq = newState(p->val + 1);
            memcpy(nq->go, q->go, sizeof q->go);
            nq->par = q->par;
            q->par = nq;
            np->par = nq;
            while (p && p->go[w] == q)
                p->go[w] = nq, p = p->par;
        }
    }
    last = np;
}

char buf[N];
int main(){
    scanf("%s", buf);
    init();
    for (char*pt = buf; *pt; ++pt)
        extend(*pt - 'a');
    scanf("%s", buf);
    State*t = root;
    int l = 0, ans = 0;
    for (char*pt = buf; *pt; ++pt){
        int w = *pt - 'a';
        if (t->go[w]){
            t = t->go[w];
            ++l;
        } else{
            while (t && !t->go[w]) t = t->par;
            if (!t) t = root, l = 0;
            else l = t->val + 1, t = t->go[w];
        }
        ans = max(ans, l);
    }

    printf("%d\n", ans);
    return 0;
}

Comments

comments powered by Disqus