Censoring 系列题解

本文主要是介绍Censoring 系列题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Censoring S/G

算法标签：字符串（KMP/AC自动机）
算法概述：这两道题其实就是一道题，无非把单模匹配变成多模匹配而已。讲讲核心思想。这题其实就是一个脑筋急转弯，谁想到了谁就A了。我们一般求KMP都是求完整个f数组，并且是对一个始终固定的文本串算f，但其实完全可以对一个栈求f数组！考虑到将一些元素弹出栈之后我们只需要让j接着栈顶那个时刻的j就可以了。所以只需要在基本的kmp的基础上，找到一个f=len(模式串)就top-=len，在计算f时用jj[top]记录栈顶top时刻的j，而f数组则是对于栈中字符串来计算的。
AC自动机上是相似的，只需要在跳的时候找到第一个vis[j]>0的j这就是我们需要删的字符串，同样的top-=len[j]并维护jj即可。
附注：G题要记忆化一下每一个trie节点跳到的位置。
代码：S/G

这篇关于Censoring 系列题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！