SPOJ1811 LCS

2015.01.16 11:02 Fri| 7 visits oi_2015| 2015_刷题日常| Text

Solution

艾玛,终于能写出来后缀自动机了 TAT

后缀自动机不得不说理解(ban dong bu dong)之后比后缀数组好写得多……

Code

#include <bits/stdc++.h>
using namespace std;

struct suffix_automaton_node
{
    int len;
    suffix_automaton_node *son[26], *par;
    suffix_automaton_node(int _len = 0) : len(_len), son(), par() {}
};

struct suffix_automaton
{
    typedef suffix_automaton_node node;
    node *root, *last;
    suffix_automaton() { last = root = new node(); }

    void insert(int c)
    {
        node *p = last, *np = new node(p->len + 1);
        while (p && p->son[c] == NULL)
            p->son[c] = np, p = p->par;
        if (!p) np->par = root;
        else
        {
            node *q = p->son[c];
            if (q->len == p->len + 1)
                np->par = q;
            else
            {
                node *nq = new node(p->len + 1);
                memcpy(nq->son, q->son, sizeof nq->son);
                nq->par = q->par;
                np->par = q->par = nq;
                while (p && p->son[c] == q)
                    p->son[c] = nq, p = p->par;
            }
        }
        last = np;
    }
    int query(char *str)
    {
        int re = 0, t = 0;
        node *pos = root;
        while (*str)
        {
            int c = *str - 'a';
            if (pos->son[c])
                pos = pos->son[c], ++t;
            else
            {
                while (pos && !pos->son[c]) pos = pos->par;
                if (pos)
                    t = pos->len + 1, pos = pos->son[c];
                else
                    pos = root, t = 0;
            }
            re = max(re, t); ++str;
        }
        return re;
    }
};

#define N 2500005
char str[N], str2[N];
suffix_automaton sam;

int main()
{
    scanf("%s%s", str, str2);
    for (int i = 0; str[i]; ++i)
        sam.insert(str[i] - 'a');
    cout << sam.query(str2) << endl;
}