c - 字符串本身中最长的公共子字符串

Question

给定一个像 . 这样的字符串，"geekthegeertheregeers"所以我们必须在字符串本身中找到最长的公共子字符串。

就像在这种情况下"geer"将是最长的公共子字符串。我的问题是这里将应用哪种算法。可以修改 LCS 以找到此问题的解决方案吗？

score 2 · Accepted Answer

问题是“在子字符串集中查找最长的子字符串不止一次”吗？“geekthegeertheregeers”的结果应该是“egeer”？

如果是这样，您可以为输入字符串构建后缀数组，并为后缀数组构建 LCP(Longest Common Prefix) 数组。两者都可以在 O(N) 中完成（N 是输入字符串的长度）。

参考：

1 回答 1