BZOJ2780 [SPOJ8093]Sevenk Love Oimaster

2015.01.22 13:33 Thu| 4 visits oi_2015| 2015_刷题日常| Text

Solution

严正声明 + 鄙视:

这道题如果直接套用水过无数类似题的后缀数组就会 TLE!

首先对原串建立广义后缀树(插入每一个串开头之前都将后缀自动机的 last 指向 root),之后可以发现对于一个询问串,询问等价于求在后缀树上以它为根的子树中节点分别归属于多少不同的子串。这一问题可以求出 DFS 序后利用树状数组简单的维护(参见 HH 的项链)(要是想用莫队的话……没人拦你

//谁说这种题用指针写不了什么什么的?

Code

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

#define N 220005
#define M 60005

struct suffix_automaton_node
{
    int len, bel; suffix_automaton_node *son[128], *pre;
    suffix_automaton_node(int _len = 0, int _bel = 0)
    : len(_len), bel(_bel), son(), pre() {}
    inline void* operator new(size_t size);
};

suffix_automaton_node nodes[N], *P = nodes;
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 endstr() { last = root; }
    void insert(int c, int b)
    {
        node *p = last, *np = new node(p->len + 1, b);
        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;
    }
    inline node *query(char* str)
    {
        node *t = root;
        for (int i = 0; str[i]; ++i)
        {
            t = t->son[(int)str[i]];
            if (t == NULL) return NULL;
        }
        return t;
    }
};

struct fenwick_tree
{
    int f[N];
    inline void modify(int x, int y)
    {
        for (int i = x; i < N; i += i & -i)
            f[i] += y;
    }
    inline int query(int x)
    {
        int re = 0;
        for (int i = x; i; i -= i & -i)
            re += f[i];
        return re;
    }
};

suffix_automaton sam;
fenwick_tree bit;

int head[N];
struct data { int next, to; } edge[N];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt].to = y;
    edge[cnt].next = head[x];
    head[x] = cnt;
}

int n, m, lpos[N], rpos[N], id[N], last[N], ans[M]; char str[N];
vector< pair<int, int> > v[N];

int tot;
void dfs(int x)
{
    lpos[x] = ++tot, id[tot] = x;
    for (int i = head[x]; i; i = edge[i].next)
        dfs(edge[i].to);
    rpos[x] = tot;
}

int main()
{
    typedef suffix_automaton_node node;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", str);
        for (int j = 0; str[j]; ++j)
            sam.insert(str[j], i);
        sam.endstr();
    }
    for (node *i = nodes + 1; i != P; ++i)
        add(i->pre - nodes, i - nodes);
    dfs(0);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%s", str);
        node *x = sam.query(str);
        if (x)
            v[rpos[x - nodes]].push_back(make_pair(lpos[x - nodes], i));
    }
    for (int now = 0, i = 1; i <= tot; ++i)
    {
        if (nodes[id[i]].bel)
        {
            if (last[nodes[id[i]].bel])
                bit.modify(last[nodes[id[i]].bel], -1);
            else ++now;
            bit.modify(i, 1); last[nodes[id[i]].bel] = i;
        }
        for (vector< pair<int, int> >::iterator j = v[i].begin();
                j != v[i].end(); ++j)
            ans[j->second] = now - bit.query(j->first - 1);
    }
    for (int i = 1; i <= m; ++i)
        printf("%d\n", ans[i]);
    return 0;
}