字符串匹配问题,考虑使用kmp解决。
和普通匹配问题不同的是,需要在匹配成功时删除模式串。即在kmp中,考虑在匹配成功时如何进行下一次匹配。
整个过程可以用栈维护,遍历文本串,依次入栈,匹配成功则出栈 ∣T∣|T|∣T∣ 个元素。此时需要考虑,下一次匹配 s[i]s[i]s[i] 应该和 TTT 的哪一个字符匹配?
和当前栈顶位置的文本串字符 所能匹配到的最大的位置 开始,这个数据可以在kmp过程中记录。
注册一个 菜鸟OJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 菜鸟OJ 通用账户