Google: Write a program to return the longest repeating substring in a string.

BinaryWitch

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

Write a program to return the longest repeating substring in a string.
eg. for "ababab", "abab" is the longest repeating substring.

guiqicj

看了帖子后自己实现了一下suffix trie, 参见https://github.com/BruceChaun/SuffixTrie

wugoat

没有太明白逻辑 abab为啥是ababab的LRS呢

BinaryWitch

wugoat 发表于 2012-7-31 16:55
没有太明白逻辑 abab为啥是ababab的LRS呢

这个是贴题的人给的例子 (abab)ab 和 ab(abab) 这样

whatever

本帖最后由 whatever 于 2012-8-1 00:40 编辑

KMP算法？字符串匹配？

xutopia

本帖最后由 xutopia 于 2015-1-28 03:19 编辑

我只知道建个suffix tree找最深的non leaf node可破，写不写的出来就是另外一回事了。。

Edit: 不知道怎么挖坟了orz，不好意思。。

akatsuki521

可以用suffix数组，然后排序，结果结果肯定在相邻的string中，挨个测一遍就ok了

[字符串] Google: Write a program to return the longest repeating substring in a string.