算法标签:字符串(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