[ABC268Ex] Taboo Solution

更好的阅读体验戳此进入

题面

给定仅有英文小写字母的字符串 $S$$S$，可以对其进行若干次操作，每次将 $S$$S$ 中某个字符替换为 *。给定 $n$$n$ 个仅有英文小写字母的模式串，要求进行操作使得 $S$$S$ 中不存在任意子串与模式串相同。最小化操作次数，输出最小值。

Solution

提供一个理论复杂度正确但因常数以及哈希原因无法通过的做法，同时略提正解。

首先我们不难想到，我们若对 $S$$S$ 匹配模式串 $T$$T$，显然若匹配到了，那么我们直接将匹配到的部分的最后一位改为 * 即可，贪心正确性显然，若改前面的可能会存在后面再次匹配使得不优。

然后对于所有匹配，我们也不难想到处理的顺序可以是先处理长度较小的串，然后再处理较长的。此处的贪心正确性仍显然，因为短的串处理时一定会尽量地破坏长的串，总之感性理解一下。

所以就不难想到一个做法，开一个 map < int, unordered_set < unsigned long long > >，对每个长度的串映射一个 set 存储所有该长度的模式串的哈希值，然后按序跑一遍，通过维护哈希来 $O(n)$$O(n)$ 跑一遍并匹配与替换。

分析一下这个的复杂度，显然每种长度都会跑一遍 $O(n)$$O(n)$，那么卡此做法的构造应使长度为等差数列，而等差数列求和是 $O(n^2)$$O(n^2)$ 级别的，所以最多的长度种类为 $O(\sqrt{\sum T_i})$$O(\sqrt{\sum T_i})$，也就是说最终复杂度是根号级别的。不过此时我们会发现这俩都是 5e5 级别的，似乎过不了？但是再看一眼时限 $4\mathtt{\text{s}}$$4\texttt{s}$，又似乎刚好能过。

不过实现之后会发现，部分测试点 WA，部分 TLE，TLE 的部分大概用了 $10\mathtt{\text{s}}$$10\texttt{s}$，若改为 unsigned int 时间可以到 $7\mathtt{\text{s}}$$7\texttt{s}$，但是同时也存在问题即哈希碰撞。我们自然可可以通过手写挂链或双模数等以使得满足正确性，但是时间上理性分析一下，等差数列实际是 ${\displaystyle \frac{n^2}{2}}$$\dfrac{n^2}{2}$ 的，所以此时还有个 $2$$2$ 倍常数，所以时间两倍之后寄掉也就很合理了。如果卡的不够死的话理论上还是可以改过的，但是也只是理论上，有兴趣可以尝试一下。

这里浅提一下正解，考虑刚才提到的贪心策略之后对于将所有模式串匹配掉直接写一个 AC自动机 即可，具体实现可以考虑如果一个节点的 fail 存在模式串那么该节点也认为是可以匹配的，也就是按照之前的贪心，优先去匹配更短的串。

Code

理论复杂度正确但无法通过的代码

xxxxxxxxxx
82
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define BASE (31ll)
23
#define S(i) (S.at(i - 1))
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
string S;
30
map < int, unordered_set < unll > > pat;
31
unll pow_base[510000];
32
int ans(0);
33

34
int main(){
35
    // freopen("in.txt", "r", stdin);
36
    pow_base[0] = 1;
37
    for(int i = 1; i <= 501000; ++i)pow_base[i] = pow_base[i - 1] * BASE;
38
    ios::sync_with_stdio(false);
39
    cin >> S;
40
    cin >> N;
41
    for(int i = 1; i <= N; ++i){
42
        string T;
43
        cin >> T;
44
        unll hashv(0);
45
        for(auto c : T)(hashv *= BASE) += c;
46
        pat[(int)T.length()].insert(hashv);
47
    }
48
    for(auto mp : pat){
49
        if(mp.first > (int)S.length())continue;
50
        unll cur(0);
51
        bool newStr(true);
52
        for(int i = 1; i <= mp.first - 1; ++i)(cur *= BASE) += S(i);
53
        for(int i = mp.first; i <= (int)S.length(); ++i){
54
            if(!newStr)cur -= S(i - mp.first) * pow_base[mp.first - 1];
55
            cur *= BASE; cur += S(i); newStr = false;
56
            if(mp.second.find(cur) != mp.second.end()){
57
                S(i) = '*', cur = 0, newStr = true, ++ans;
58
                if(i + mp.first > (int)S.length())break;
59
                for(int j = i + 1; j <= i + mp.first - 1; ++j)(cur *= BASE) += S(j);
60
                i = i + mp.first - 1;
61
            }
62
        }
63
    }printf("%d\n", ans);
64
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
65
    return 0;
66
}
67

68
template < typename T >
69
inline T read(void){
70
    T ret(0);
71
    int flag(1);
72
    char c = getchar();
73
    while(c != '-' && !isdigit(c))c = getchar();
74
    if(c == '-')flag = -1, c = getchar();
75
    while(isdigit(c)){
76
        ret *= 10;
77
        ret += int(c - '0');
78
        c = getchar();
79
    }
80
    ret *= flag;
81
    return ret;
82
}

正解代码

xxxxxxxxxx
99
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Node::operator new(size_t){static Node* P = nd; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define d(c) (c - 'a')
23

24
template < typename T = int >
25
inline T read(void);
26

27
struct Node{
28
    Node* son[26];
29
    Node* fail;
30
    int cnt;
31
    OPNEW;
32
}nd[510000];
33
ROPNEW;
34
Node* root;
35

36
int N;
37
int ans(0);
38
string S;
39
basic_string < Node* > tmp;
40

41
void Insert(string S){
42
    Node* cur = root;
43
    for(auto c : S){
44
        if(!cur->son[d(c)])cur->son[d(c)] = new Node();
45
        cur = cur->son[d(c)];
46
    }cur->cnt++;
47
}
48
void Build(void){
49
    queue < Node* > cur; cur.push(root);
50
    while(!cur.empty()){
51
        auto p = cur.front(); cur.pop();
52
        for(int i = 0; i <= 25; ++i)
53
            if(p->son[i]){
54
                cur.push(p->son[i]), tmp += p->son[i];
55
                if(p == root)p->son[i]->fail = root;
56
                else p->son[i]->fail = p->fail->son[i];
57
            }else{
58
                if(p == root)p->son[i] = root;
59
                else p->son[i] = p->fail->son[i];
60
            }
61
    }
62
}
63
void SetFail(void){
64
    for(auto p : tmp)p->cnt += p->fail->cnt;
65
}
66
void Accept(void){
67
    Node* cur = root;
68
    for(auto c : S){
69
        cur = cur->son[d(c)];
70
        if(cur->cnt)++ans, cur = root;
71
    }
72
}
73

74
int main(){
75
    root = new Node();
76
    cin >> S;
77
    N = read();
78
    for(int i = 1; i <= N; ++i){string T; cin >> T; Insert(T);}
79
    Build(), SetFail(), Accept();
80
    printf("%d\n", ans);
81
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
82
    return 0;
83
}
84

85
template < typename T >
86
inline T read(void){
87
    T ret(0);
88
    int flag(1);
89
    char c = getchar();
90
    while(c != '-' && !isdigit(c))c = getchar();
91
    if(c == '-')flag = -1, c = getchar();
92
    while(isdigit(c)){
93
        ret *= 10;
94
        ret += int(c - '0');
95
        c = getchar();
96
    }
97
    ret *= flag;
98
    return ret;
99
}

UPD

update-2023_01_18 初稿

update-2023_01_23 补充了一些关于正解的思路以及正解的代码