BZOJ 3942 [Usaco2015 Feb]Censoring

发布于 2017-06-17  180 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3942

题意:给定串 S 和串 T,按顺序将串 S 中的字符加入串 U,若串 U 的后缀为串 T,则删除此后缀...


可以用一个栈来维护串 U,一边 KMP 扫串 S 一遍压栈,匹配成功则弹栈,然而弹栈后不能直接继续扫串 S,因为可能上下剩余的两部分串又合成了一个 T 串,那么我们需要额外再开一个栈,和原栈同进同出,维护指针下标即可,匹配成功后跳过去...

 


一个非常弱的准退役OIER