1 条题解

  • 0
    @ 2024-4-5 2:38:50

    字符串匹配问题,考虑使用kmp解决。

    和普通匹配问题不同的是,需要在匹配成功时删除模式串。即在kmp中,考虑在匹配成功时如何进行下一次匹配。

    整个过程可以用栈维护,遍历文本串,依次入栈,匹配成功则出栈 T|T| 个元素。此时需要考虑,下一次匹配 s[i]s[i] 应该和 TT 的哪一个字符匹配?

    和当前栈顶位置的文本串字符 所能匹配到的最大的位置 开始,这个数据可以在kmp过程中记录。

    • 1

    信息

    ID
    43
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者