https://cn.vjudge.net/problem/HDU-3695
跟2222几乎一样，求文本中出现了多少个模式串，但是数据量变大了，5e6的长度。这时候用原来的写法已经会tle了，看到别人说用打标记的方式记录trie上一个节点有没有走过，一开始是不理解的，为什么这么做是正确的？后来想了想，AC自动机的算法确定了一个起点之后，沿着fail回溯的路径便已经确定（神奇），所以这条路上被走过的单词尾，再走的时候就会重复，而我们可以简单的把走过的节点计数标志变为-1，而在之后的过程中再遇到就可以不用管这个节点及其之后所有的节点了。注意这个是在while一开始就得判断。
WA的话，是从带括号的那个原串解压过后忘了在最后加’\0’。。。emmmm以后试验这种一定要从大到小试验数据。还有就是模板一定要用自己熟悉的。。原来以为这题问题在于kuangbin的板子不够快后来发现是没标记。。第二个是一开始没意识到q可以不止1位。。
继续阅读“[AC自动机][字符串][模板][优化] HDU3695 Computer Virus on Planet Pandora”
https://cn.vjudge.net/problem/HDU-5880
AC自动机模板题，不过判断是否是禁忌串内的这种标记方法还是值得一看的。
主要是理解了AC自动机的板子。。当时比赛没有把这个题写出来也是挫了，其实就是模板题。有一个需要注意的地方是如果禁忌串互相包含怎么操作，这里参考的大佬代码用的pos-1和+1标记是否在括号内的做法，很舒服。
错误的话，把Trie开到main里RE。。本地都RE，然后每个test都要换行，忘了这个PE了一发。
这个题有很多做法，目前先用二分+KMP过了，二分的原理是如果最大字串存在那么这个最大字串的字串也一定满足要求。难得1Y，明天用后缀数组尝试一下来填坑。。
学习了一下这个算法，emmm不知道什么时候就会用到的感觉。本身功能是在O(n)时间内算出一个串的最长回文子串，其实这个过程也把每个点作为中心的最长回文串计算了一遍
这个算法的话主要是利用回文串的性质，回头整理好了再详细写。
大概复习了下，裸的kmp，其实这个对我来说重点不是kmp而是学到的新快读挂。。。当发现自己裸读800ms，加快读挂140ms然后前排聚聚还是能90ms的时候就去翻了下他们代码然后发现了这个神奇的，，我本地 甚至不能正常运行的快读。。Oooooooorz。。。
继续阅读“[字符串] kmp模板题 HDU1711”
