【C++】Bzoj3942 Censoring

2021-06-19 08:03

阅读：407

标签：算法 ash 重点是你就是 int 子串 tchar put

这一题改一改\(KMP\)算法就可以过了，但是你需要对KMP有足够的了解。

先膜一波\(AC\)自动机和字符串\(Hash\)的大佬。

\(O(n)\)开了\(O_2\)优化后进了第三（截至目前），跑的还是挺快的。

\(KMP\)问题的核心在于数组\(next\)(或者\(pre\)/\(fail\)，各种叫法)，几乎所有的此类型题都是需要计算\(next\)的。

这里解释一波\(next\):即满足字符子串\(s[1...k]=s[j-k+1...j]\)的最大\(k\)。比如说：

字符串\(abaca\)的\(next[5]\)就是\(1\)，因为只有\(s[1]=s[5]\)。

而字符串\(abcab\)的\(next[5]\)就是2，同理，\(s[1...2]=s[4...5]\)。

弄清楚了这一点，来看题目，显然，这道题的难点在于删除字符后有可能对前面已经匹配完了的字符产生新一次的匹配，因为后面新加入的字符可能对前面的字符有贡献。

既然这样，我们不妨设一下四个变量:\(i,j,k,l\)（所有字符串从\(0\)开始）。

其中\(i,l\)表示当前需要将\(S_i\)加入到\(U_l\)中，\(j\)表示当前匹配到了\(T_j\)，\(k\)表示当前已经匹配到\(U_k\)。

如果当\(k==l\)时，代表前\(k-1\)个字符已经匹配完，添加新字符。
接下来就是调整\(next\)和判断是否匹配，同普通\(KMP\)算法。
！！重点：当\(j==lenT\)即已经匹配完了，则将\(j\)归零，将\(l\)减去\(lenT\)示删去了\(lenT\)个字符，因为\(l\)就是新串的长度，接下来，我们直接将\(k\)减去\(lenT\times 2\)因为前面最多会有\(lenT-1\)个字符与\(T\)匹配，特判一下当\(k时将\(k\)置为\(0\)就可以了。

#include 
#include 

const int Len = 1e6 + 10;
char S[Len], T[Len], U[Len];
int lenS, lenT, nxt[Len];

void init () {
    for (int i = 1, j = 0; i

【C++】Bzoj3942 Censoring

标签：算法 ash 重点是你就是 int 子串 tchar put

原文地址：https://www.cnblogs.com/water-mi/p/9690874.html

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【C++】Bzoj3942 Censoring
文章链接：http://soscw.com/essay/95853.html

亲，登录后才可以留言！