gpt4 book ai didi

c - 字符串本身的最长公共(public)子串

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:07:42 24 4
gpt4 key购买 nike

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

在这种情况下,"geer" 将是最长的公共(public)子串。我的问题是这里将应用哪种算法。是否可以修改 LCS 以找到此问题的解决方案?

最佳答案

是“查找最长子串在子串集中出现多次”的问题吗?“geekthegeertheregeers”的结果应该是“egeer”?

如果是,则可以为输入字符串构建后缀数组,为后缀数组构造LCP(Longest Common Prefix)数组。两者都可以在 O(N) 中完成(N 是输入字符串的长度)。

引用:

  1. 后缀数组 ( http://en.wikipedia.org/wiki/Suffix_array )
  2. LCP 阵列 ( http://en.wikipedia.org/wiki/LCP_array )

关于c - 字符串本身的最长公共(public)子串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20028480/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com