无动态规划或后缀树的最长公共子串

Question

Skiena的算法设计手册问题8-3 b部分要求给出一个“更简单”的BigO(nm)算法，用于寻找不依赖于动态编程的最长公共子字符串。显而易见的答案似乎是使用后缀树，然而，Skiena使用了“更简单”这个词，我不确定后缀树是否比DP更简单，也许搜索更简单，但在nm时间复杂度内构建后缀树一点也不简单。所以，我想知道，有没有其他方法可以在O(nm)时间内解决这个问题？

Answer 1

假设我们固定了第一个(较短)字符串s中的起始位置i。现在让我们在更长的字符串中找到它可能最长的前缀。这可以在O(n + m)中通过检查字符串s[i:] + # + t的prefix function(或z function)来完成，其中#是在任何s和t中都不存在的特殊符号。

总体复杂度为O(n(n + m))，当nO(nm)