g家电面

hxtang 发表于 2016-9-14 09:05
brute-force的可以遍历所有可能的子串首字符s和循环节长度l，复杂度是O(n^3)

优化的时候对每个l，似乎可 ...

你说的这个优化可以讲的更仔细一点吗？

感觉优化的的话要用trie树来做

hxtang 发表于 2016-9-14 09:05
brute-force的可以遍历所有可能的子串首字符s和循环节长度l，复杂度是O(n^3)

优化的时候对每个l，似乎可 ...

你这里说的brute-force的要O(N^4)吧

aangel 发表于 2016-9-14 12:25
你这里说的brute-force的要O(N^4)吧

我的理解是找重复>k次的循环串...

如果只是有没有找重复次数>k次的子串的话，只要找有没有重复次数>k次的字符就行了，这个扫一遍数据对每个字符的频率计数就能搞定.

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

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

这个方法好机智！

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

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

那如果你找到了呢？

hyliu0000 发表于 2016-9-14 23:47
那如果你找到了呢？

问题不就是判断能不能找到吗？找到了返回true，没找到返回false呀。。。

hxtang 发表于 2016-9-14 23:53
问题不就是判断能不能找到吗？找到了返回true，没找到返回false呀。。。

a1a23a456a789

这里面有重复次数大于k的连续子串吗？

hyliu0000 发表于 2016-9-14 23:57
a1a23a456a789

这里面有重复次数大于k的连续子串吗？

你没有specify k = ?
如果k＝4的话，子串不就是a吗？

hxtang 发表于 2016-9-15 00:00
你没有specify k = ?
如果k＝4的话，子串不就是a吗？

你看到连续两个字了吗？