Skiena的算法设计手册问题8-3 b部分要求给出一个“更简单”的BigO（nm）算法，用于找到不依赖于动态编程的最长公共子串。显而易见的答案似乎是使用后缀树，但是，Skiena使用“Simpler”这个词我不确定后缀树比DP简单，也许搜索更简单，但是在nm时间复杂度下建立后缀树是什么，但是简单。所以，我想知道，有没有另一种方法可以在O（nm）时间内解决这个问题？
让我们说我们在第一个（较短的）字符串i中修复起始位置s。现在让我们在较长的字符串中找到它最长的前缀。它可以通过检查字符串O(n + m)的prefix function（或z function）在s[i:] + # + t中完成，其中＃是s和t中不存在的特殊符号。
总体复杂性是O(n(n + m))，如果n <m，则为O(nm)