重复出现次数最多的子串中最长的子串

面试题

找重复出现次数最多的子串中最长的那个子串。例:
“abcdabc” 2次abc
“bbbb” 4次b

思路:
记录每个长度的字串重复出现的次数,然后找到出现次数最多的所有字串,返回最长的那个。

如,abcdabc,长度为1的字串有a:2,b:2,c:2,d:1,长度为2的字串有ab:2,bc:2,ca:1,长度为3的字串有abc:2,bcd:1,cda:1,dab:1,长度为4的有abcd:1,bcda:1,dabc:1,长度为5的有abcda:1,bcdab:1,cdabc:1,长度为6的有abcdab:1,bcdabc:1,长度为7的有abcdabc:1。其中出现最多的是2次,有a:2,b:2,c:2, ab:2,bc:2, abc:2。其中长度最长的是abc

因此可以这样写:

听说是Leecode上的题目,我搜到了一些用后缀数组解法的,但并没有看明白,上面这种方法也是最笨的方法,不知道还有什么复杂度更低的方法。


“重复出现次数最多的子串中最长的子串”的5个回复

Loading...
  1. 沙发!
    常规思路,但效率较差。
    这种在网站里一般用在自动提取标签上,找到文本中出现频率最高的5个字符串,提取作为标签。
    目前绝大多网站用的都是标签字典,类似于搜索引擎那种,所以效率很高。
    至于不依赖外部字典自动提取……我记得有什么方法,但忘了……

    1. 又仔细看了下,貌似这题出的有些奇怪,和标签提取还不是一回事……
      “找重复出现次数最多的子串中最长的那个子串”,首先是“出现次数最多”,其次才是“最长的字符串”。
      那例如“abcdabca”这段中肯定是“a”出现次数最多,这么看来貌似你那答案蛮不错的……

发表评论

电子邮件地址不会被公开。 必填项已用*标注