[ABC268Ex] Taboo Solution
目录更好的阅读体验戳此进入
题面
给定仅有英文小写字母的字符串 $ S $，可以对其进行若干次操作，每次将 $ S $ 中某个字符替换为 *。给定 $ n $ 个仅有英文小写字母的模式串，要求进行操作使得 $ S $ 中不存在任意子串与模式串相同。最小化操作次数，输出最小值。
Solution
提供一个理论复杂度正确但因常数以及哈希原因无法通过的做法，同时略提正解。
首先我们不难想到，我们若对 $ S $ 匹配模式串 $ T $，显然若匹配到了，那么我们直接将匹配到的部分的最后一位改为 * 即可，贪心正确性显然，若改前面的可能会存在后面再次匹配使得不优。
然后对于所有匹配，我们也不难想到处理的顺序可以是先处理长度较小的串，然后再处理较长的。此处的贪心正确性仍显然，因为短的串处理时一定会尽量地破坏长的串，总之感性理解一下。
所以就不难想到一个做法，开一个 map < int, unordered_set < unsigned long long > >，对每个长度的串映射一个 set 存储所有该长度的模式串的哈希值，然后按序跑一遍，通过维护哈希来 $ O(n) $ 跑一遍并匹配与替换。
分析一下这个的复杂度，显然每种长度都会跑一遍 $ O(n) $，那么卡此做法的构造应使长度为等差数列，而等差数列求和是 $ O(n^2) $ 级别的，所以最多的长度种类为 $ O(\sqrt{\sum T_i}) $，也就是说最终复杂度是根号级别的。不过此时我们会发现这俩都是 5e5 级别的，似乎过不了？但是再看一眼时限 $ 4\texttt{s} $，又似乎刚好能过。
不过实现之后会发现，部分测试点 WA，部分 TLE，TLE 的部分大概用了 $ 10\texttt{s} $，若改为 unsigned int 时间可以到 $ 7\texttt{s} $，但是同时也存在问题即哈希碰撞。我们自然可可以通过手写挂链或双模数等以使得满足正确性，但是时间上理性分析一下，等差数列实际是 $ \dfrac{n^2}{2} $ 的，所以此时还有个 $ 2 $ 倍常数，所以时间两倍之后寄掉也就很合理了。如果卡的不够死的话理论上还是可以改过的，但是也只是理论上，有兴趣可以尝试一下。
这里浅提一下正解，考虑刚才提到的贪心策略之后对于将所有模式串匹配掉直接写一个 AC自动机 即可，具体实现可以考虑如果一个节点的 fail 存在模式串那么该节点也认为是可以匹配的，也就是按照之前的贪心，优先去匹配更短的串。
Code
理论复杂度正确但无法通过的代码
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define BASE (31ll)
#define S(i) (S.at(i - 1))
template < typename T = int >
inline T read(void);
int N;
string S;
map < int, unordered_set < unll > > pat;
unll pow_base[510000];
int ans(0);
int main(){
// freopen("in.txt", "r", stdin);
pow_base[0] = 1;
for(int i = 1; i <= 501000; ++i)pow_base[i] = pow_base[i - 1] * BASE;
ios::sync_with_stdio(false);
cin >> S;
cin >> N;
for(int i = 1; i <= N; ++i){
string T;
cin >> T;
unll hashv(0);
for(auto c : T)(hashv *= BASE) += c;
pat[(int)T.length()].insert(hashv);
}
for(auto mp : pat){
if(mp.first > (int)S.length())continue;
unll cur(0);
bool newStr(true);
for(int i = 1; i <= mp.first - 1; ++i)(cur *= BASE) += S(i);
for(int i = mp.first; i <= (int)S.length(); ++i){
if(!newStr)cur -= S(i - mp.first) * pow_base[mp.first - 1];
cur *= BASE; cur += S(i); newStr = false;
if(mp.second.find(cur) != mp.second.end()){
S(i) = '*', cur = 0, newStr = true, ++ans;
if(i + mp.first > (int)S.length())break;
for(int j = i + 1; j <= i + mp.first - 1; ++j)(cur *= BASE) += S(j);
i = i + mp.first - 1;
}
}
}printf("%d\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
正解代码
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define d(c) (c - 'a')
template < typename T = int >
inline T read(void);
struct Node{
Node* son[26];
Node* fail;
int cnt;
OPNEW;
}nd[510000];
ROPNEW;
Node* root;
int N;
int ans(0);
string S;
basic_string < Node* > tmp;
void Insert(string S){
Node* cur = root;
for(auto c : S){
if(!cur->son[d(c)])cur->son[d(c)] = new Node();
cur = cur->son[d(c)];
}cur->cnt++;
}
void Build(void){
queue < Node* > cur; cur.push(root);
while(!cur.empty()){
auto p = cur.front(); cur.pop();
for(int i = 0; i <= 25; ++i)
if(p->son[i]){
cur.push(p->son[i]), tmp += p->son[i];
if(p == root)p->son[i]->fail = root;
else p->son[i]->fail = p->fail->son[i];
}else{
if(p == root)p->son[i] = root;
else p->son[i] = p->fail->son[i];
}
}
}
void SetFail(void){
for(auto p : tmp)p->cnt += p->fail->cnt;
}
void Accept(void){
Node* cur = root;
for(auto c : S){
cur = cur->son[d(c)];
if(cur->cnt)++ans, cur = root;
}
}
int main(){
root = new Node();
cin >> S;
N = read();
for(int i = 1; i <= N; ++i){string T; cin >> T; Insert(T);}
Build(), SetFail(), Accept();
printf("%d\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2023_01_18 初稿
update-2023_01_23 补充了一些关于正解的思路以及正解的代码
标签：Node,cur,int,题解,void,son,ABC268Ex,Taboo,define From： https://www.cnblogs.com/tsawke/p/17124350.html