三种做法：BZOJ 2780: [Spoj]8093 Sevenk Love Oimaster

时间：2021-10-14 04:22:31

@

题意

链接：here

有\(n\)个大串\(s\)和\(m\)个询问，每次给出一个字符串\(t\)询问在多少个大串中出现过。

\(1\le n\le 10000,1\le m\le 60000,\sum|s|\le 100000,\sum |t|\le 360000\)

思路

初步分析

  • 对\(n\)个串建广义后缀自动机（每个串插入子前将当前节点归为到根节点即可）。
  • 询问即把询问串\(t\)一步步在后缀自动机上走即可，走到节点\(p\)，若\(p\)为\(0\)，则答案为\(0\)。
  • 反之，答案即为后缀连接树上\(p\)节点子树内不同颜色数。
  • 上述颜色数解释为：将\(n\)个串设为\(n\)种颜色，将串\(i\)包含的所有节点添加\(i\)这种颜色，一个节点可能包含很多颜色。

法1：广义后缀自动机+玄学的暴力？

  • 看不懂这样写的复杂度，跑得飞快？有人说是\(O(n\sqrt n)\)，但是跑得比\(O(nlog(n))\)和\(O(n)\)还快。。
  • 对\(n\)个串跑一边广义后缀自动机。
  • 对后缀自动机里的每个节点记录一下上一个经过他的是哪一个字符串以及有多少字符串经过这个字符串。
  • 可是这个要咋维护呢？在线\(or\)离线？
  • 玄学做法：每插入一个节点后，沿着他的后缀连接向根节点暴力跑，更新贡献，遇到节点\(p\)上一次被经过的串也是这个串时，则\(break\)。

法2：广义后缀自动机+set启发式合并

  • 每个节点用\(set\)储存经过他的字符串种类，然后把后缀连接树建出来，自叶子节点向上\(set\)启发式合并即可。
  • 我感觉复杂度应该比\(nlog(n)\)要大一点吧，也不会超过\(nlog(n)^2\)。

法3：广义后缀自动机+dfs序+离线树状数组

  • 这就是一个套路做法了，很常见的离线树状数组应用吧？
  • 继续初步分析的讨论，跑一遍\(dfs\)序后查询子树问题就变成了查询序列的一段区间类似问题了。
  • 那就把所有询问离线下来，按查询右端点排序。
  • 把树按\(dfs\)序变成一个序列，从头开始遍历，树状数组更新颜色数量，为保证一种颜色的贡献只计算一次，记录一下每种颜色上一次更新的位置，这里更加，那里减即可。（这个套路可以看我博客里一些树状数组题解即可。
  • 当已处理过得元素不少于询问的右端点时，即开始查询答案。
  • 感觉很常见啊。。

嘤嘤嘤

AC_Code1

#pragma comment(linker, "/STACK:102400000,102400000")

#include<bits/stdc++.h>

#define fi first

#define se second

#define endl '\n'

#define o2(x) (x)*(x)

#define BASE_MAX 30

#define mk make_pair

#define eb emplace_back

#define all(x) (x).begin(), (x).end()

#define clr(a, b) memset((a),(b),sizeof((a)))

#define iis std::ios::sync_with_stdio(false); cin.tie(0)

#define my_unique(x) sort(all(x)),x.erase(unique(all(x)),x.end())

using namespace std;

#pragma optimize("-O3")

typedef long long LL;

typedef pair<int, int> pii;

inline LL read() {

    LL x = 0;int f = 0;

    char ch = getchar();

    while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();

    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();

    return x = f ? -x : x;

}

inline void write(LL x) {

    if (x == 0) {putchar('0'), putchar('\n');return;}

    if (x < 0) {putchar('-');x = -x;}

    static char s[23];

    int l = 0;

    while (x != 0)s[l++] = x % 10 + 48, x /= 10;

    while (l)putchar(s[--l]);

    putchar('\n');

}

int lowbit(int x) { return x & (-x); }

template<class T>T big(const T &a1, const T &a2) { return a1 > a2 ? a1 : a2; }

template<typename T, typename ...R>T big(const T &f, const R &...r) { return big(f, big(r...)); }

template<class T>T sml(const T &a1, const T &a2) { return a1 < a2 ? a1 : a2; }

template<typename T, typename ...R>T sml(const T &f, const R &...r) { return sml(f, sml(r...)); }

void debug_out() { cerr << '\n'; }

template<typename T, typename ...R>void debug_out(const T &f, const R &...r) {cerr << f << " ";debug_out(r...);}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__);

#define print(x) write(x);

const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;

const int HMOD[] = {1000000009, 1004535809};

const LL BASE[] = {1572872831, 1971536491};

const int mod = 998244353;

const int MOD = 1e9 + 7;

const int INF = 0x3f3f3f3f;

const int MXN = 5e5 + 5;

const int MXE = 5e6 + 6;

int n, m;

char s[MXN];

int sum[MXN], pre[MXN];

struct Suffix_Automaton {

    static const int maxn = 5e5 + 105;

    //basic

//    map<char,int> nex[maxn * 2];

    int nex[maxn*2][26];

    int link[maxn * 2], len[maxn * 2];

    int last, cnt;

    LL tot_c;//不同串的个数

    void clear() {

        tot_c = 0;

        last = cnt = 1;

        link[1] = len[1] = 0;

//        nex[1].clear();

        memset(nex[1], 0, sizeof(nex[1]));

    }

    void add(int c, int id) {

        int p = last;

        int np = ++cnt;

//        nex[cnt].clear();

        memset(nex[cnt], 0, sizeof(nex[cnt]));

        len[np] = len[p] + 1;

        last = np;

        while (p && !nex[p][c])nex[p][c] = np, p = link[p];

        if (!p)link[np] = 1, tot_c += len[np] - len[link[np]];

        else {

            int q = nex[p][c];

            if (len[q] == len[p] + 1)link[np] = q, tot_c += len[np] - len[link[np]];

            else {

                int nq = ++cnt;

                len[nq] = len[p] + 1;

//                nex[nq] = nex[q];

                memcpy(nex[nq], nex[q], sizeof(nex[q]));

                link[nq] = link[q];

                link[np] = link[q] = nq;

                sum[nq] = sum[q] , pre[nq] = pre[q];

                tot_c += len[np] - len[link[np]];

                while (nex[p][c] == q)nex[p][c] = nq, p = link[p];

            }

        }

        for(p = np; p && pre[p] != id; p = link[p]) pre[p] = id, ++ sum[p];

    }

} sam;

int main() {

#ifndef ONLINE_JUDGE

    freopen("/home/cwolf9/CLionProjects/ccc/in.txt", "r", stdin);

    //freopen("/home/cwolf9/CLionProjects/ccc/out.txt", "w", stdout);

#endif

//    int Tim = read();

    n = read(), m = read();

    sam.clear();

    for(int i = 1; i <= n; ++i) {

        sam.last = 1;

        scanf("%s", s);

        int ln = strlen(s);

        for(int j = 0; j < ln; ++j) sam.add(s[j] - 'a', i);

    }

    while(m --) {

        scanf("%s", s);

        int u = 1, ln = strlen(s);

        for(int i = 0; i < ln; ++i) u = sam.nex[u][s[i] - 'a'];

        printf("%d\n", sum[u]);

    }

#ifndef ONLINE_JUDGE

    cout << "time cost:" << 1.0*clock()/CLOCKS_PER_SEC << "ms" << endl;

#endif

    return 0;

}

AC_Code2

const int MXN = 2e5 + 5;

const int MXE = 4e5 + 6;

int n, m;

char s[MXE];

int sum[MXN], pre[MXN];

set<int> orz[MXN];

vector<int> mp[MXN];

struct Suffix_Automaton {

    static const int maxn = 2e5 + 105;

    //basic

//    map<char,int> nex[maxn * 2];

    int nex[maxn*2][26];

    int link[maxn * 2], len[maxn * 2];

    int last, cnt;

    LL tot_c;//不同串的个数

    void clear() {

        tot_c = 0;

        last = cnt = 1;

        link[1] = len[1] = 0;

//        nex[1].clear();

        memset(nex[1], 0, sizeof(nex[1]));

    }

    void add(int c, int id) {

        int p = last;

        int np = ++cnt;

//        nex[cnt].clear();

        memset(nex[cnt], 0, sizeof(nex[cnt]));

        len[np] = len[p] + 1;

        last = np;

        orz[np].insert(id);

        while (p && !nex[p][c])nex[p][c] = np, p = link[p];

        if (!p)link[np] = 1, tot_c += len[np] - len[link[np]];

        else {

            int q = nex[p][c];

            if (len[q] == len[p] + 1)link[np] = q, tot_c += len[np] - len[link[np]];

            else {

                int nq = ++cnt;

                len[nq] = len[p] + 1;

//                nex[nq] = nex[q];

                memcpy(nex[nq], nex[q], sizeof(nex[q]));

                link[nq] = link[q];

                link[np] = link[q] = nq;

                tot_c += len[np] - len[link[np]];

                while (nex[p][c] == q)nex[p][c] = nq, p = link[p];

            }

        }

//        for(p = np; p && pre[p] != id; p = link[p]) pre[p] = id, ++ sum[p];

    }

} sam;

set<int>::iterator sit;

void dfs(int u) {

    for(int i = 0, v; i < (int)mp[u].size(); ++ i) {

        v = mp[u][i];

        dfs(v);

        if((int)orz[v].size() > (int)orz[u].size()) swap(orz[u], orz[v]);

        for(sit = orz[v].begin(); sit != orz[v].end(); ++ sit) orz[u].insert(*sit);

    }

    sum[u] = (int)orz[u].size();

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("/home/cwolf9/CLionProjects/ccc/in.txt", "r", stdin);

    //freopen("/home/cwolf9/CLionProjects/ccc/out.txt", "w", stdout);

#endif

//    int Tim = read();

    n = read(), m = read();

    sam.clear();

    for(int i = 1; i <= n; ++i) {

        sam.last = 1;

        scanf("%s", s);

        int ln = strlen(s);

        for(int j = 0; j < ln; ++j) sam.add(s[j] - 'a', i);

    }

    for(int i = 2; i <= sam.cnt; ++i) mp[sam.link[i]].push_back(i);

    dfs(1);

    while(m --) {

        scanf("%s", s);

        int u = 1, ln = strlen(s);

        for(int i = 0; i < ln; ++i) u = sam.nex[u][s[i] - 'a'];

        printf("%d\n", sum[u]);

    }

#ifndef ONLINE_JUDGE

    cout << "time cost:" << 1.0*clock()/CLOCKS_PER_SEC << "ms" << endl;

#endif

    return 0;

}

AC_Code3

const int MXN = 4e5 + 5;

const int MXE = 4e5 + 6;

int n, m;

char s[MXE];

int sum[MXN], pre[MXN], bit[MXN];

vector<int> mp[MXN], orz[MXN];

int did[MXN], rid[MXN], lid[MXN], inde;

void bit_add(int x, int v, int N) {

    while(x <= N) {

        bit[x] += v;

        x += lowbit(x);

    }

}

int bit_query(int x) {

    if(x < 0) return 0;

    int res = 0;

    while(x) {

        res += bit[x];

        x -= lowbit(x);

    }

    return res;

}

struct Suffix_Automaton {

    static const int maxn = 2e5 + 105;

    //basic

//    map<char,int> nex[maxn * 2];

    int nex[maxn*2][26];

    int link[maxn * 2], len[maxn * 2];

    int last, cnt;

    void clear() {

        last = cnt = 1;

        link[1] = len[1] = 0;

//        nex[1].clear();

        memset(nex[1], 0, sizeof(nex[1]));

    }

    void add(int c, int id) {

        int p = last;

        int np = ++ cnt;

//        nex[cnt].clear();

        memset(nex[cnt], 0, sizeof(nex[cnt]));

        len[np] = len[p] + 1;

        last = np;

        orz[np].push_back(id);

        while (p && !nex[p][c]) nex[p][c] = np, p = link[p];

        if (!p) link[np] = 1;

        else {

            int q = nex[p][c];

            if (len[q] == len[p] + 1) link[np] = q;

            else {

                int nq = ++cnt;

                len[nq] = len[p] + 1;

//                nex[nq] = nex[q];

                memcpy(nex[nq], nex[q], sizeof(nex[q]));

                link[nq] = link[q];

                link[np] = link[q] = nq;

                while (nex[p][c] == q)nex[p][c] = nq, p = link[p];

            }

        }

//        for(p = np; p && pre[p] != id; p = link[p]) pre[p] = id, ++ sum[p];

    }

} sam;

struct lp {

    int l, r, id;

}cw[MXN];

void dfs(int u) {

    did[u] = ++ inde, rid[inde] = u;

    for(int i = 0, v; i < (int)mp[u].size(); ++ i) {

        v = mp[u][i];

        dfs(v);

    }

    lid[u] = inde;

}

bool cmp(const lp&a,const lp&b) {

    if(a.r != b.r) return a.r < b.r; return a.l < b.l;

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("/home/cwolf9/CLionProjects/ccc/in.txt", "r", stdin);

    //freopen("/home/cwolf9/CLionProjects/ccc/out.txt", "w", stdout);

#endif

//    int Tim = read();

    n = read(), m = read();

    sam.clear();

    for(int i = 1; i <= n; ++i) {

        sam.last = 1;

        scanf("%s", s);

        int ln = strlen(s);

        for(int j = 0; j < ln; ++j) sam.add(s[j] - 'a', i);

    }

    for(int i = 2; i <= sam.cnt; ++i) mp[sam.link[i]].push_back(i);

    dfs(1);

    for(int i = 1; i <= m; ++i) {

        scanf("%s", s);

        int u = 1, ln = strlen(s);

        for(int j = 0; j < ln; ++j) u = sam.nex[u][s[j] - 'a'];

        cw[i].id = i, cw[i].l = did[u], cw[i].r = lid[u];

        if(u == 1) cw[i].l = cw[i].r = -1, sum[i] = 0;

//        debug(cw[i].l, cw[i].r)

    }

    sort(cw + 1, cw + 1 + m, cmp/*[](const lp&a,const lp&b){ if(a.r != b.r) return a.r < b.r; return a.l < b.l;}*/);

    int j = 1;

    while(cw[j].l == -1 && j <= m) ++ j;

    for(int i = 2; i <= inde; ++i) {

        for(int j = 0, x; j < (int)orz[rid[i]].size(); ++j) {

            x = orz[rid[i]][j];

            bit_add(i, 1, sam.cnt);

            if(pre[x]) bit_add(pre[x], -1, sam.cnt);

            pre[x] = i;

        }

        while(j <= m && cw[j].r <= i) {

            sum[cw[j].id] = bit_query(cw[j].r) - bit_query(cw[j].l - 1);

            ++ j;

        }

    }

    for(int i = 1; i <= m; ++i) printf("%d\n", sum[i]);

#ifndef ONLINE_JUDGE

    cout << "time cost:" << 1.0*clock()/CLOCKS_PER_SEC << "ms" << endl;

#endif

    return 0;

}

参考

/*

 * http://wyfcyx.is-programmer.com/posts/76391.html

 * https://www.wandouip.com/t5i167692/

 * http://www.voidcn.com/article/p-kbhgnkio-oh.html

 * https://eolv.farbox.com/post/oi_2015/bzoj2780

 * http://blog.miskcoo.com/2015/05/bzoj-2780

 * https://www.cnblogs.com/CQzhangyu/p/7088404.html

 */

bzoj 2780: [Spoj]8093 Sevenk Love Oimaster

相关文章