当前位置:首页 > 字符串 > AC自动机 > 正文
SSOJ2761Censoring
1828+

题目大意:一篇文章,从里面删除n个屏蔽词,一旦找到立即删除,删除后重头找起,请问最终剩下的内容是什么?

题目描述

原题来自:USACO 2015 Feb. Gold

有一个长度不超过 105 的字符串 S。Farmer John 希望在 S 中删掉 n 个屏蔽词(一个屏蔽词可能出现多次),这些词记为 t1tn

FJ 在 S 中从头开始寻找屏蔽词,一旦找到一个屏蔽词,FJ 就删除它,然后又从头开始寻找(而不是接着往下找)。FJ 会重复这一过程,直到 S 中没有屏蔽词为止。注意删除一个单词后可能会导致 S 中出现另一个屏蔽词。这 n 个屏蔽词不会出现一个单词是另一个单词子串的情况,这意味着每个屏蔽词在 S 中出现的开始位置是互不相同的,请帮助 FJ 完成这些操作并输出最后的 S

输入

第一行包含一个字符串 S
第二行包含一个整数 n
接下来的 n 行,每行包含一个字符串,第 i 行的字符串是 ti

输出

一行,输出操作后的 S。保证 S 不会变成空串。

提示

样例输入

begintheescapexecutionatthebreakofdawn
2
escape
execution

样例输出

beginthatthebreakofdawn

对于全部数据,1ti105,1S105,保证所有字符串只出现小写字母。

解题思路

与AC自动机模板不同的是,文章是“动态”的,删除一个单词后,后面的内容需要接到前面去。为了避免重新匹配,我们可以一边查找,一边记录每个字符匹配到字典树的哪一个节点,并保存到q数组。逐个字符匹配,放入新的字符串,遇到匹配,弹出若干个字符;全部删除完成后,输出新的字符串。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

SSOJ2761Censoring:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!