给定一个像 "geekthegeerthereegeers" 这样的字符串。所以我们必须找到字符串本身的最长公共(public)子串。
就像在这种情况下“geer”将是最长的公共(public)子字符串。
我的问题是这里将应用哪种算法。可以修改 LCS 来找到这个问题的解决方案吗？
最佳答案
问题“查找最长子串在子串集中出现多次”吗？ “geekthegeertheregeers”的结果应该是“egeer”？
如果是这样，您可以为输入字符串构建后缀数组，并为后缀数组构建LCP(最长公共(public)前缀)数组。两者都可以在 O(N) 内完成(N 是输入字符串的长度)。
引用:
- 后缀数组 ( http://en.wikipedia.org/wiki/Suffix_array )
- LCP 阵列 ( http://en.wikipedia.org/wiki/LCP_array )
关于c - 字符串本身的最长公共(public)子串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20028480/