s*l
6 楼
suffix tree
http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
【在 B********t 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 给个字符串S,判断它是不是某个字符串T复制K次的结果。K未知,T未知。不要n^2的解
: 。。
A*o
9 楼
sort
B*t
10 楼
好像是这么回事。
【在 s*********l 的大作中提到】![](/moin_static193/solenoid/img/up.png)
:
: suffix tree
: http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
【在 s*********l 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
:
: suffix tree
: http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
l*8
11 楼
设字符串S长度为N。
取K为N的质数因子,然后求解。
取K为N的质数因子,然后求解。
p*2
12 楼
KMP吧。
p*2
21 楼
我这个已经做过了。在我的博客里有。你们看看吧。
http://blog.sina.com.cn/s/blog_b9285de20101ipa9.html
http://blog.sina.com.cn/s/blog_b9285de20101ipa9.html
j*y
29 楼
楼主面试官是老中吗?
【在 s*******i 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: http://poj.org/problem?id=2406
【在 s*******i 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: http://poj.org/problem?id=2406
r*n
31 楼
用suffix array应该可以做,但是提升也不大,因为要sort,所以是O(nlogn)
f*t
33 楼
咦,kmp估計是正解,感覺還有個nlogn的算法好像也還將就。
掃一遍字符串統計各字符出現次數,得到一個stat[]數組
如果只有一種字符而字符串長度大於一,return true
else
求stat所有值的最大公約數(nlogn),假設為gcd
if gcd==1,return false
否則,如果存在一種重複T構造S的方法的話,gcd一定是K的因子
而無論K等於gcd的多少倍,S能分成K份就一定能分成gcd份(因為gcd
只能是K的因子)
然後檢測K=gcd,S是否符合要求,符合返回true,否則return false(O(n))
實際上上面的的nlogn複雜度遠遠達不到的~~仔細分析也許會跟kmp的正解差不多?
掃一遍字符串統計各字符出現次數,得到一個stat[]數組
如果只有一種字符而字符串長度大於一,return true
else
求stat所有值的最大公約數(nlogn),假設為gcd
if gcd==1,return false
否則,如果存在一種重複T構造S的方法的話,gcd一定是K的因子
而無論K等於gcd的多少倍,S能分成K份就一定能分成gcd份(因為gcd
只能是K的因子)
然後檢測K=gcd,S是否符合要求,符合返回true,否則return false(O(n))
實際上上面的的nlogn複雜度遠遠達不到的~~仔細分析也許會跟kmp的正解差不多?
a*o
34 楼
顶这个,个人觉得这个才是goog想要的
【在 f******t 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 咦,kmp估計是正解,感覺還有個nlogn的算法好像也還將就。
: 掃一遍字符串統計各字符出現次數,得到一個stat[]數組
: 如果只有一種字符而字符串長度大於一,return true
: else
: 求stat所有值的最大公約數(nlogn),假設為gcd
: if gcd==1,return false
: 否則,如果存在一種重複T構造S的方法的話,gcd一定是K的因子
: 而無論K等於gcd的多少倍,S能分成K份就一定能分成gcd份(因為gcd
: 只能是K的因子)
: 然後檢測K=gcd,S是否符合要求,符合返回true,否則return false(O(n))
【在 f******t 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 咦,kmp估計是正解,感覺還有個nlogn的算法好像也還將就。
: 掃一遍字符串統計各字符出現次數,得到一個stat[]數組
: 如果只有一種字符而字符串長度大於一,return true
: else
: 求stat所有值的最大公約數(nlogn),假設為gcd
: if gcd==1,return false
: 否則,如果存在一種重複T構造S的方法的話,gcd一定是K的因子
: 而無論K等於gcd的多少倍,S能分成K份就一定能分成gcd份(因為gcd
: 只能是K的因子)
: 然後檢測K=gcd,S是否符合要求,符合返回true,否則return false(O(n))
b*u
35 楼
应该k是gcd的因子吧
【在 f******t 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 咦,kmp估計是正解,感覺還有個nlogn的算法好像也還將就。
: 掃一遍字符串統計各字符出現次數,得到一個stat[]數組
: 如果只有一種字符而字符串長度大於一,return true
: else
: 求stat所有值的最大公約數(nlogn),假設為gcd
: if gcd==1,return false
: 否則,如果存在一種重複T構造S的方法的話,gcd一定是K的因子
: 而無論K等於gcd的多少倍,S能分成K份就一定能分成gcd份(因為gcd
: 只能是K的因子)
: 然後檢測K=gcd,S是否符合要求,符合返回true,否則return false(O(n))
【在 f******t 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 咦,kmp估計是正解,感覺還有個nlogn的算法好像也還將就。
: 掃一遍字符串統計各字符出現次數,得到一個stat[]數組
: 如果只有一種字符而字符串長度大於一,return true
: else
: 求stat所有值的最大公約數(nlogn),假設為gcd
: if gcd==1,return false
: 否則,如果存在一種重複T構造S的方法的話,gcd一定是K的因子
: 而無論K等於gcd的多少倍,S能分成K份就一定能分成gcd份(因為gcd
: 只能是K的因子)
: 然後檢測K=gcd,S是否符合要求,符合返回true,否則return false(O(n))
相关阅读
Apple Graphics and Camera Software Teams hiring (转载)Facebook怎么又换了UI了?支付宝招BD Manager需要懂西班牙语如何确保每次读入的字符串都是unique的 (转载)10个包子求解这道题难不难?我今天发现yelp又一个猥琐的行为 (转载)一个offer贴引发的Facebook未来的争论组里的阿三伪造数据,文章竟然发表了! (转载)有没有朋友一起刷题?相互监督?Amex SPG卡送25K points 免费送500刀现金 最佳酒店卡如果想自学转软件工程师应该怎么做呢 ?那张H1B百分比的图片,是说中国学生每年只有7000多人能工作么?leetcode经典题分类复习 by 菜木鸟 [祝大家offer滚滚] --- 资源请教在monster.com上放简历的问题加州公司都那么变态有个ACM ICPC 2003 world finalist 要加我linkedin求救:CPT renew的时间晚了,怎么办 (转载)Process or Device Engineer 求内推_个人背景 材料,器件