求助站外题

学术版

Register_int @ 2022-10-12 22:53:34

给定一个小写串 s 以及 n 个小写串 t_{1\sim n}，在 s 中修改最少的字符为 *，是的所有 t 都不会在 s 中出现。

这里我是用 AC 自动机做的，找出所有 t 在 s 中的位置，问题转化为：给定一些区间，放置尽量少的点，使得每个区间中都有点。但是这个区间数量是 O(n^2) 级别。求优化

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

int ch[MAXN][26], fail[MAXN], tot;

int elen[MAXN];

inline 
void insert(char *s) {
    int len = strlen(s), k = 0;
    for (int i = 0; i < len; i++) {
        if (!ch[k][s[i] - 'a']) ch[k][s[i] - 'a'] = ++tot;
        k = ch[k][s[i] - 'a'];
    }
    elen[k] = len;
}

inline 
void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (ch[0][i]) q.push(ch[0][i]);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            if (ch[u][i]) fail[ch[u][i]] = ch[fail[u]][i], q.push(ch[u][i]);
            else ch[u][i] = ch[fail[u]][i];
        }
    }
}

int maxr, ans;

inline 
void find(char *s) {
    int len = strlen(s), k = 0;
    for (int i = 0; i < len; i++) {
        k = ch[k][s[i] - 'a'];
        for (int p = k; p; p = fail[p]) {
            if (elen[p] && i - elen[p] + 2 > maxr) ans++, maxr = i + 1;
        }
    }
}

int n, m;

char s[MAXN], t[MAXN];

int main() {
    scanf("%s%d", s, &m), n = strlen(s);
    for (int i = 1; i <= m; i++) scanf("%s", t), insert(t);
    build(), find(s);
    printf("%d", ans);
}

by sdqe @ 2022-10-12 23:11:12

任意两个区间 [a, b] [c, d] 当 d = b 时，只需要保留较长的，所以最多只会有 n 个区间。对于 s 的每个 i 只需要保留比较长的那个串，在 fail 树上维护一下 maxlen 就可以

by FutaRimeWoawaSete @ 2022-10-12 23:12:58

@Register_int 对于 [l,r] 中 r 相同的保留 l 最大的那个即可。

by 狂风之息 @ 2022-10-13 06:46:45

@Register_int 我的想法是直接在 AC 自动机上面跑匹配，一旦完成匹配就将 ans+1，然后把匹配的指针跳回根节点（也就是把当前位换成 *）

by Register_int @ 2022-10-13 19:58:52

@狂风之息寄掉了，复杂度大概率是假的。 @oOoOoOOOooOO @Hakuoro 感谢两位大佬回答 %%% 但是还是想请教一下怎么维护最小长度 qwq 蒟蒻不会 qwq

by FutaRimeWoawaSete @ 2022-10-13 20:03:49

@Register_int 对于所有的 t 建广义后缀自动机，对于 s 暴力维护每个后缀 [1,i] 在 SAM 上的最短匹配区间 [l,i]，这个直接用树上倍增维护即可。

by Register_int @ 2022-10-13 20:07:56

@Hakuoro 感谢大佬！！！但感觉解法有点复杂了，直接哈希暴力枚举能过 qwq
这里附个原题链接 https://atcoder.jp/contests/abc268/tasks/abc268_h?lang=en

by FutaRimeWoawaSete @ 2022-10-13 20:29:49

@Register_int 直接胡的，没细想。你的暴力 hash 是指直接暴力枚举位置吗。那时间复杂度还是有点问题吗。

我毛估估会一个根号分治过后的 hash 做，但是时间复杂度还是根号了。

by FutaRimeWoawaSete @ 2022-10-13 20:33:28

@Register_int 而且甚至广义后缀自动机做可以线性找区间。然后只要写一个基数排序之类的也能线性做这道题，貌似是这样的（

by sdqe @ 2022-10-13 23:18:10

@Register_int 如果 trie 树上某个节点 u 是一个结尾，则F[u] = len(u)，不然 F[u] = F[fail[u]]。

by sdqe @ 2022-10-13 23:45:59

@oOoOoOOOooOO @Register_int 上面写少了取 min。

int f[MAXN];

inline
void build()
{
    queue<int> q;
    for (int i = 0; i < 26; i++)
    {
        if (ch[0][i]) q.push(ch[0][i]);
    }
    f[0] = inf;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        f[u] = inf;
        if(elen[u])f[u] = min(elen[u], f[fail[u]]);
        else f[u] = f[fail[u]];
        for (int i = 0; i < 26; i++)
        {
            if (ch[u][i]) fail[ch[u][i]] = ch[fail[u]][i], q.push(ch[u][i]);
            else ch[u][i] = ch[fail[u]][i];
        }
    }
}