BZOJ1396&BZOJ2865 识别子串

2015.01.16 15:41 Fri| 6 visits oi_2015| 2015_刷题日常| Text

Solution

这么久,终于搞明白了后缀自动机和后缀树的关系:

后缀自动机的 pre 树其实就是逆向的后缀树(前缀树?),后缀树中一条边上压缩的字符串的就是在后缀自动机上这条边所跨越的字符节点。

//我这只 sx 想了好久好久……

(发明后缀自动机这个大神的脑子是怎么长的 -_-||

显然,在后缀树中每一个叶子节点到其父亲的边上所表示的字符串都是识别子串。

对于一个字符,答案是以下两部分的长度最小值:

  • 包含这一字符的极短识别子串
  • 在极短识别子串的基础上扩展出的子串

对于每一部分可以分别用并查集或线段树(好写好调的说...)维护。

//明明是双倍经验题,为什么还卡内存 QAQ

//开了 850000 个后缀自动机节点,满意了吧……

Code

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

struct suffix_automaton_node
{
    int len; bool leaf;
    suffix_automaton_node *son[26], *pre;
    suffix_automaton_node(int _len = 0) : len(_len), leaf(true), son(), pre() {}
    inline void *operator new(size_t size);
};

suffix_automaton_node newnode[850005], *P = newnode;
inline void *suffix_automaton_node::operator new(size_t size) { return P++; }

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->pre;
        if (!p) np->pre = root;
        else
        {
            node *q = p->son[c];
            if (q->len == p->len + 1)
                np->pre = q;
            else
            {
                node *nq = new node(p->len + 1);
                memcpy(nq->son, q->son, sizeof nq->son);
                nq->pre = q->pre;
                np->pre = q->pre = nq;
                while (p && p->son[c] == q)
                    p->son[c] = nq, p = p->pre;
            }
        }
        last = np;
    }
};


struct segment_tree
{
#define lson (pos << 1)
#define rson (pos << 1 | 1)
#define inf 0x3f3f3f3f
    int mint[N * 3], lazy[N * 3];
    segment_tree()
    {
        memset(mint, 0x3f, sizeof mint);
        memset(lazy, 0x3f, sizeof lazy);
    }
    inline void update(int pos, int x)
    {
        lazy[pos] = min(lazy[pos], x);
        mint[pos] = min(mint[pos], x);
    }
    void modify(int pos, int l, int r, int x, int y, int z)
    {
        if (x <= l && r <= y) { update(pos, z); return; }
        int mid = (l + r) >> 1;
        if (lazy[pos] != inf)
        {
            update(lson, lazy[pos]), update(rson, lazy[pos]);
            lazy[pos] = inf;
        }
        if (x <= mid) modify(lson, l, mid, x, y, z);
        if (y > mid) modify(rson, mid + 1, r, x, y, z);
    }
    int query(int pos, int l, int r, int x)
    {
        if (l == r) return mint[pos];
        int mid = (l + r) >> 1;
        if (lazy[pos] != inf)
        {
            update(lson, lazy[pos]), update(rson, lazy[pos]);
            lazy[pos] = inf;
        }
        if (x <= mid) return query(lson, l, mid, x);
        else return query(rson, mid + 1, r, x);
    }
};

char str[N];
segment_tree s1, s2;
suffix_automaton sam;


int main()
{
    scanf("%s", str);
    int n = strlen(str);
    for (int i = 0; i < n; ++i)
        sam.insert(str[i] - 'a');
    for (suffix_automaton_node *i = newnode + 1; i != P; ++i)
        i->pre->leaf = false;
    for (suffix_automaton_node *i = newnode + 1; i != P; ++i)
        if (i->leaf)
        {
            int y = i->len, x = y - i->pre->len;
            s1.modify(1, 1, n, x, y, y - x + 1);
            if (x > 1) s2.modify(1, 1, n, 1, x - 1, y);
        }
    for (int i = 1; i <= n; ++i)
        printf("%d\n", min(s1.query(1, 1, n, i), s2.query(1, 1, n, i) - i + 1));
}