Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「BZOJ 2555」SubString - SAM + LCT

  1. 在当前字符串的后面插入一个字符串;
  2. 询问字符串 s s 在当前字符串中出现了几次?(作为连续子串)

链接

BZOJ 2555

题解

在线查询字符串的出现次数,需要在线维护 end-pos \text{end-pos} 集合的大小。使用 Link-Cut Tree 维护有根树的子树和。每次 Link 两个节点后,重新将根节点置为有根树的根,然后将子节点的权值加到父节点到根的一条链上;反之,Cut 后要将其减去。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 600000;
const int MAXL = 3000000;
const int MAXM = 10000;
const int CHARSET_SIZE = 26;

struct LinkCutTree {
    struct Node {
        Node *ch[2], *fa, *pathFa;
        int val, tag;
        bool rev;

        int relation() {
            return this == fa->ch[1];
        }

        void pushDown() {
            if (rev) {
                rev ^= 1;
                std::swap(ch[0], ch[1]);
                if (ch[0]) ch[0]->rev ^= 1;
                if (ch[1]) ch[1]->rev ^= 1;
            }

            if (tag) {
                if (ch[0]) ch[0]->add(tag);
                if (ch[1]) ch[1]->add(tag);
                tag = 0;
            }
        }

        void rotate() {
            pushDown();

            int r = relation();
            Node *o = fa;

            std::swap(pathFa, o->pathFa);

            fa = o->fa;
            if (o->fa) o->fa->ch[o->relation()] = this;

            o->ch[r] = ch[r ^ 1];
            if (ch[r ^ 1]) ch[r ^ 1]->fa = o;

            ch[r ^ 1] = o;
            o->fa = this;
        }

        void splay() {
            while (fa) {
                if (fa->fa) fa->fa->pushDown();
                fa->pushDown();

                if (!fa->fa) rotate();
                else if (fa->relation() == relation()) fa->rotate(), rotate();
                else rotate(), rotate();
            }
        }

        void expose() {
            splay();
            pushDown();
            if (ch[1]) {
                std::swap(ch[1]->fa, ch[1]->pathFa);
                ch[1] = NULL;
            }
        }

        bool splice() {
            splay();
            if (!pathFa) return false;

            pathFa->expose();
            pathFa->ch[1] = this;
            std::swap(pathFa, fa);

            return true;
        }

        void access() {
            expose();
            while (splice());
        }

        void evert() {
            access();
            splay();
            rev ^= 1;
        }

        void add(int delta) {
            val += delta;
            tag += delta;
        }
    } N[MAXN * 2 + 1];

    void link(int fa, int ch) {
        Node *f = &N[fa], *c = &N[ch];

        f->evert();
        c->splay();
        c->pathFa = f;

        N[0].evert();

        f->access();
        f->splay();
        f->val += c->val;
        if (f->ch[0]) f->ch[0]->add(c->val);
    }

    void cut(int fa, int ch) {
        Node *f = &N[fa], *c = &N[ch];

        f->evert();
        c->access();
        f->splay();
        f->pushDown();

        f->ch[1] = NULL;
        c->fa = NULL;

        N[0].evert();

        f->access();
        f->splay();
        f->val -= c->val;
        if (f->ch[0]) f->ch[0]->add(-c->val);
    }

    void update(int u, int val) {
        N[u].val = val;
    }

    int query(int u) {
        Node *a = &N[u];
        a->splay();
        return a->val;
    }
} lct;

struct SuffixAutomaton {
    struct Node {
        Node *ch[CHARSET_SIZE], *next;
        int max;

        Node(int max = 0) : ch(), next(NULL), max(max) {}
    } *start, *last, _pool[MAXN * 2 + 1], *_curr;

    void init() {
        _curr = _pool;
        start = last = new (_curr++) Node;
    }

    int id(Node *v) {
        return v - _pool;
    }

    Node *extend(int c) {
        Node *u = new (_curr++) Node(last->max + 1), *v = last;
        lct.update(id(u), 1);

        do {
            v->ch[c] = u;
            v = v->next;
        } while (v && !v->ch[c]);

        if (!v) {
            u->next = start;

            lct.link(id(start), id(u));
        } else if (v->ch[c]->max == v->max + 1) {
            u->next = v->ch[c];

            lct.link(id(v->ch[c]), id(u));
        } else {
            Node *n = new (_curr++) Node(v->max + 1), *o = v->ch[c];
            std::copy(o->ch, o->ch + CHARSET_SIZE, n->ch);

            lct.cut(id(o->next), id(o));
            lct.link(id(o->next), id(n));
            lct.link(id(n), id(o));
            lct.link(id(n), id(u));

            n->next = o->next;
            o->next = u->next = n;
            for (; v && v->ch[c] == o; v = v->next) v->ch[c] = n;
        }

        last = u;
        return u;
    }
} sam;

char s[MAXL + 2];
int len;

inline void decode(int mask) {
    for (int i = 0; i < len; i++) {
        mask = (mask * 131 + i) % len;
        std::swap(s[i + 1], s[mask + 1]);
    }
}

inline void extend() {
    for (int i = 1; i <= len; i++) sam.extend(s[i] - 'A');
}

inline int solve() {
    SuffixAutomaton::Node *v = sam.start;
    for (int i = 1; i <= len; i++) {
        int c = s[i] - 'A';
        if (!v->ch[c]) return 0;
        v = v->ch[c];
    }
    return lct.query(sam.id(v));
}

int main() {
    int q;
    scanf("%d", &q);

    sam.init();

    scanf("%s", s + 1);
    len = strlen(s + 1);
    extend();

    int mask = 0;
    while (q--) {
        char type[sizeof("QUERY")];
        scanf("%s %s", type, s + 1);

        len = strlen(s + 1);
        decode(mask);
        // puts(s + 1);
        if (type[0] == 'Q') {
            int ans = solve();
            printf("%d\n", ans);
            mask ^= ans;
        } else {
            extend();
        }
    }

    return 0;
}
更早的文章

「TJOI2015」弦论 - SAM