g家电面

例如k=4，是要连续4个某个子串例如abc么？ abcabcabcabc 才返回true？

如果是这样的话我觉得就两个指针p1 从 0 -> len - 1,  p2 从 p1 -> len - 1 假设我们想要的是[p1, p2)这一段重复，那么p1,p2所在的字符必定相同
所以如果p1,p1所在字符相同就判断从p1开始[p1,p2)这一段是否重复k次，重复了就返回true, 否则继续，当然p1,p2不需要走到最后，到后面没可能了就提前结束

时间复杂度是O(n^2 * k) 不知道有没有更好地解法， （还是我题意理解错了？）

jacky841102 发表于 2016-9-16 00:52
感觉可以用suffix array + LCP(Longest common prefix)

http://www.geeksforgeeks.org/suffix-array-set ...

请问下这中方法， 怎么保证找到的子串是连续的呢？

楼主， 可不可以举个例子？ 题意有点不清晰啊

fatalme 发表于 2016-9-14 06:18
Prefix tree可以 O(N^2)复杂度。

N^2直接暴力也是这个复杂度吧，何必搞这么复杂。。。

补充内容 (2016-10-4 03:44):
这个不对，请忽略，我当时以为是不需要连续

hxtang 发表于 2016-9-15 06:53
外层for loop遍历所有可能的循环节长度l
内层for loop从i=l开始数连续满足str==str的i的个数。如果个数> ...

这个不对吧，应该还是O(n^3)，因为他们没说对于输入字符串必须要从第一个字符开始就开始这个连续重复K次的字串
比如cdefababab如果k等于2的话，后面那个ababab也是算的，所以你说的这个循环外面还要加一层，就是起始字符从第0个开始，第一个开始，第二个开始，所以还是O(n^3)

liurudahai 发表于 2016-10-4 03:43
这个不对吧，应该还是O(n^3)，因为他们没说对于输入字符串必须要从第一个字符开始就开始这个连续重复K次 ...

假设第n个字母跟第n-k相同就画一个x，那么
cdefababab
          xxxx
可以看到有4个连续的x，所以循环子串一共6个字母，循环3次