BZOJ 3942 [Usaco2015 Feb]Censoring


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

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


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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3942 [Usaco2015 Feb]Censoring


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,