g家电面

hxtang 发表于 2016-9-15 06:43
那就是10楼说的brute force O(n3)，可以优化成两层循环O(n2)。不知道有没有更快的。

这个优化到O（N^2)用什么实现呢

aangel 发表于 2016-9-15 06:45
这个优化到O（N^2)用什么实现呢

外层for loop遍历所有可能的循环节长度l
内层for loop从i=l开始数连续满足str[i]==str[i-l]的i的个数。如果个数>=(k-1)l，则返回true
(str是输入串）

比如abab，k=2
l=2时，str[2]==str[0], str[3]==str[1]，所以返回true

hxtang 发表于 2016-9-14 21:15
我的理解是找重复>k次的循环串...

如果只是有没有找重复次数>k次的子串的话，只要找有没有重复次数>k ...

对的，就是这个思路

补充内容 (2016-9-15 23:41):
但有重复次数>k的字母，并不一定有重复次数>k的连续循环串。不过你说的这个思路是优化剪枝的点之一

hxtang 发表于 2016-9-15 00:06
这个就是我14楼问的...不知道这个题的意思是找occurrence > k 的任意子串，还是循环至少k次的循环子串
...

是循环至少k次的连续子串

uha714 发表于 2016-9-15 23:42
是循环至少k次的连续子串

楼主举个例子嘛。。。

uha714 发表于 2016-9-15 23:42
是循环至少k次的连续子串

lz能讲一下最优算法的复杂度吗，比较好奇能不能好于O(n2)

谢谢lz，比较好奇能不能好于O(logn)

感觉可以用suffix array + LCP(Longest common prefix)

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

suffix array 是把长度为n的字串的n个suffix排列后的array

如banana 的 suffix array:
i    [i:]
2   a
3   ana
1   anana  
0   banana  
4   na   
2   nana

LCP 是记录suffix array中相邻suffix的最长共同prefix
https://en.wikipedia.org/wiki/LCP_array

i    [i:]         LCP
2   a             ---
3   ana          1
1   anana       3
0   banana     0
4   na            0
2   nana         2

注意
4   na           0
2   nana        2
会有重复k次的连续子字串话，LCP array 会出现以0或是--为首，长度为k的等差数列
如在banana中    na 和 nana，等差是2
如果是abcabcabc    abc, abcabc, abcabcabc会在suffix array中排在一起，且在LCP array中是以3为等差的数列--, 3, 6

建suffix array可达到O(nlogn)，比较容易的方法是O(n(logn)^2)
建LCP array是O(n)
找长度为k的等差数列只需扫一遍LCP array, 是O(n)

总共是O(nlogn) 或 O(n(logn)^2)

在请教一下，如果面试时被问到如何优化？那是不是应该先不要给出最优解法? 这样会有余地去优化

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

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

感觉好像有点问题，似乎不能保证相关的后缀一定出现在LCP的连续位置
比如
abaac, k = 2,应该是返回true的，但是照LCP会返回false:
i  [i:]      LCP
2 aac     -
0 abaac  1
3 ac       1
1 baac    0
4 c         0
因为aac和ac没有连在一起