c++ - 没有动态编程或后缀树的最长公共子串

Question

Skiena 的算法设计手册问题 8-3 b 部分要求给出一个“更简单”的 BigO(nm) 算法，用于查找不依赖于动态编程的最长公共子串。显而易见的答案似乎是使用后缀树，但是，Skiena 使用“更简单”这个词简单的。所以，我想知道，有没有另一种方法可以在 O(nm) 时间内解决这个问题？

Answer 1

假设我们i在 first(shorter) string 中固定了起始位置s。现在让我们在较长的字符串中找到其最长的前缀。可以O(n + m)通过检查字符串的前缀函数（或z 函数）来完成，其中 # 是特殊符号，在任何ands[i:] + # + t中都不存在。st

总体复杂度O(n(n + m))是O(nm)如果 n < m