[Usaco2015 Feb]Censoring --- AC自动机 + 栈

bzoj 3940 Censoring

题目描述

FJ把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过10^5的字符串S。

他有一个包含n个单词的列表,列表里的n个单词记为T1......Tn。他希望从S中删除这些单词。

FJ每次在S中找到最早出现的列表中的单词(最早出现指该单词的开始位置最小),然后从S中删除这个单词。

他重复这个操作直到S中没有列表里的单词为止。

注意删除一个单词后可能会导致S中出现另一个列表中的单词

FJ注意到列表中的单词不会出现一个单词是另一个单词子串的情况,这意味着每个列表中的单词在S中出现的开始位置是互不相同的

请帮助FJ完成这些操作并输出最后的S

注:FJ ---> Farmer John

输入格式:

第一行:S

第二行:n

后n行:T1......Tn

输出格式:

处理后的字符串

考虑匹配

注意到没有T串的开头相同,因此也不会有T串的结尾相同。

因此,可以放心的直接将T串建成AC自动机

把S串放进去匹配

只要匹配到T串的结尾端点就可以返回\(len(T)\)前的字符和节点继续匹配

可以选择一个一个往前回溯

也可以选择维护一个栈,一次弹多个(同时要记录匹配节点,字符,以及每个单词的长度)

代码在此

上一篇:java – 连接Netbeans和MySQL但遇到Big Integer错误


下一篇:BZOJ 3940: [Usaco2015 Feb]Censoring AC自动机_栈