没有动态规划或后缀树的最长公共子串
Longest Common Substring without Dynamic programming or Suffix Tree
Skiena's Algorithm Design Manual 第8-3题b部分要求给出一个"simpler" BigO(nm)算法，用于寻找不依赖于动态规划的最长公共子串。显而易见的答案似乎是使用后缀树，但是，Skiena 使用 "Simpler" 这个词我不确定后缀树是否比 DP 更简单，也许搜索更简单，但是在 nm 时间复杂度中构建后缀树是绝非简单。所以，我想知道，是否有另一种方法可以在 O(nm) 时间内解决这个问题？
假设我们在第一个（较短的）字符串 s 中固定了起始位置 i。现在让我们在较长的字符串中找到它可能最长的前缀。它可以在 O(n + m) 中通过检查字符串 s[i:] + # + t 的 prefix function(or z function) 来完成，其中 # 是在 s 和 t 中都不存在的特殊符号。
总体复杂度为 O(n(n + m))，如果 n < m
，则为 O(nm)
Skiena's Algorithm Design Manual 第8-3题b部分要求给出一个"simpler" BigO(nm)算法，用于寻找不依赖于动态规划的最长公共子串。显而易见的答案似乎是使用后缀树，但是，Skiena 使用 "Simpler" 这个词我不确定后缀树是否比 DP 更简单，也许搜索更简单，但是在 nm 时间复杂度中构建后缀树是绝非简单。所以，我想知道，是否有另一种方法可以在 O(nm) 时间内解决这个问题？
假设我们在第一个（较短的）字符串 s 中固定了起始位置 i。现在让我们在较长的字符串中找到它可能最长的前缀。它可以在 O(n + m) 中通过检查字符串 s[i:] + # + t 的 prefix function(or z function) 来完成，其中 # 是在 s 和 t 中都不存在的特殊符号。
总体复杂度为 O(n(n + m))，如果 n < m
O(nm)