f*e
2 楼
是这样吗？
for(int i = 0; i < S.size(); i++)
if(S[i] != T[i%T.size()]) return false;
return true;
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
for(int i = 0; i < S.size(); i++)
if(S[i] != T[i%T.size()]) return false;
return true;
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
j*y
3 楼
先算两个长度 |S| 和 |T| ,算出 K = |S| / |T|
再把 T复制 K 次， 和 S 比较 ?
O(|S| + |T|)
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
再把 T复制 K 次， 和 S 比较 ?
O(|S| + |T|)
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
j*y
4 楼
这个不对
比如 S = aba
T = ab
【在 f*****e 的大作中提到】
: 是这样吗？
: for(int i = 0; i < S.size(); i++)
: if(S[i] != T[i%T.size()]) return false;
: return true;
比如 S = aba
T = ab
【在 f*****e 的大作中提到】
: 是这样吗？
: for(int i = 0; i < S.size(); i++)
: if(S[i] != T[i%T.size()]) return false;
: return true;
B*t
5 楼
T是未知的。。
【在 j*****y 的大作中提到】
: 先算两个长度 |S| 和 |T| ,算出 K = |S| / |T|
: 再把 T复制 K 次， 和 S 比较 ?
: O(|S| + |T|)
【在 j*****y 的大作中提到】
: 先算两个长度 |S| 和 |T| ,算出 K = |S| / |T|
: 再把 T复制 K 次， 和 S 比较 ?
: O(|S| + |T|)
s*l
6 楼
suffix tree
http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
f*e
7 楼
S是T=S复制1次的结果:-)
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
B*t
8 楼
@。@ ！@#￥%……&＊（）
【在 f*****e 的大作中提到】
: S是T=S复制1次的结果:-)
【在 f*****e 的大作中提到】
: S是T=S复制1次的结果:-)
A*o
9 楼
sort
B*t
10 楼
好像是这么回事。
【在 s*********l 的大作中提到】
:
: suffix tree
: http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
【在 s*********l 的大作中提到】
:
: suffix tree
: http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
l*8
11 楼
设字符串S长度为N。
取K为N的质数因子，然后求解。
取K为N的质数因子，然后求解。
p*2
12 楼
KMP吧。
j*y
13 楼
确实用 kmp简单，和那个 storm8 的题目一样
pattern = S
source = S + S
找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
return
true, 否则 return false
【在 p*****2 的大作中提到】
: KMP吧。
pattern = S
source = S + S
找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
return
true, 否则 return false
【在 p*****2 的大作中提到】
: KMP吧。
f*e
14 楼
你题目都没说明白，一点严谨性都没有，很奇怪这么多人re你的贴。
【在 B********t 的大作中提到】
: 好像是这么回事。
【在 B********t 的大作中提到】
: 好像是这么回事。
B*t
15 楼
...........好吧....我的错. 向来语文不好 您也不要这么大火气。
【在 f*****e 的大作中提到】
: 你题目都没说明白，一点严谨性都没有，很奇怪这么多人re你的贴。
【在 f*****e 的大作中提到】
: 你题目都没说明白，一点严谨性都没有，很奇怪这么多人re你的贴。
p*p
16 楼
ababa是aba复制1次的结果还是2次的结果？
还是说复制aba得不到ababa
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
还是说复制aba得不到ababa
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
P*b
17 楼
我咋觉得两个pointer不停移就搞定了呢
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
B*t
18 楼
懂了。。知道2爷的意思了。。我太挫了
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
l*b
19 楼
nice solution indeed !
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
j*y
20 楼
kmp 可以达到线性，你这个能线性？
【在 P*******b 的大作中提到】
: 我咋觉得两个pointer不停移就搞定了呢
【在 P*******b 的大作中提到】
: 我咋觉得两个pointer不停移就搞定了呢
p*2
21 楼
我这个已经做过了。在我的博客里有。你们看看吧。
http://blog.sina.com.cn/s/blog_b9285de20101ipa9.html
http://blog.sina.com.cn/s/blog_b9285de20101ipa9.html
P*b
22 楼
O(2N)阿
【在 j*****y 的大作中提到】
: kmp 可以达到线性，你这个能线性？
【在 j*****y 的大作中提到】
: kmp 可以达到线性，你这个能线性？
Y*Y
23 楼
先算S长度n, 然后找出n所有大于1的质因子数
然后对任何一个质因子K，判断S是不是K个相同的字符串组成的。
复杂度应该接近linear,因为一个数的质因子数很少。
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
然后对任何一个质因子K，判断S是不是K个相同的字符串组成的。
复杂度应该接近linear,因为一个数的质因子数很少。
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
A*o
24 楼
不行吧，整数分解，complexity class都不定
【在 Y**Y 的大作中提到】
: 先算S长度n, 然后找出n所有大于1的质因子数
: 然后对任何一个质因子K，判断S是不是K个相同的字符串组成的。
: 复杂度应该接近linear,因为一个数的质因子数很少。
【在 Y**Y 的大作中提到】
: 先算S长度n, 然后找出n所有大于1的质因子数
: 然后对任何一个质因子K，判断S是不是K个相同的字符串组成的。
: 复杂度应该接近linear,因为一个数的质因子数很少。
l*b
25 楼
那是因为那个复杂度是按number of digits定义的,哈哈...
【在 A***o 的大作中提到】
: 不行吧，整数分解，complexity class都不定
【在 A***o 的大作中提到】
: 不行吧，整数分解，complexity class都不定
l*8
26 楼
握手
【在 Y**Y 的大作中提到】
: 先算S长度n, 然后找出n所有大于1的质因子数
: 然后对任何一个质因子K，判断S是不是K个相同的字符串组成的。
: 复杂度应该接近linear,因为一个数的质因子数很少。
【在 Y**Y 的大作中提到】
: 先算S长度n, 然后找出n所有大于1的质因子数
: 然后对任何一个质因子K，判断S是不是K个相同的字符串组成的。
: 复杂度应该接近linear,因为一个数的质因子数很少。
c*t
27 楼
就算知道解法，还必须知道并写对KMP，google面试果然比以前难了不少。
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
j*y
29 楼
楼主面试官是老中吗？
【在 s*******i 的大作中提到】
: http://poj.org/problem?id=2406
【在 s*******i 的大作中提到】
: http://poj.org/problem?id=2406
B*t
30 楼
是我同学面的题。他说听声不像。哈哈。
【在 j*****y 的大作中提到】
: 楼主面试官是老中吗？
【在 j*****y 的大作中提到】
: 楼主面试官是老中吗？
r*n
31 楼
用suffix array应该可以做，但是提升也不大，因为要sort，所以是O(nlogn)
r*n
32 楼
题目不是这个意思吧
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
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 的大作中提到】
: 咦，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 的大作中提到】
: 咦，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 的大作中提到】
: 咦，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 的大作中提到】
: 咦，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))
C*n
36 楼
同意，例如aabbaabb，gcd是4，k是2
【在 b*****u 的大作中提到】
: 应该k是gcd的因子吧
【在 b*****u 的大作中提到】
: 应该k是gcd的因子吧
h*i
37 楼
对，求gcd倒是O(n), 但是gcd的因子太多了， 如果K等于2^n * 3^m * 5^o，需要测试
的序列一点也不少。
【在 b*****u 的大作中提到】
: 应该k是gcd的因子吧
的序列一点也不少。
【在 b*****u 的大作中提到】
: 应该k是gcd的因子吧
H*s
38 楼
其实不用这么麻烦， 像二爷说的，kmp pi function 直接解决！
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
A*o
39 楼
gcd can be done in O(logn)
【在 h***i 的大作中提到】
: 对，求gcd倒是O(n), 但是gcd的因子太多了， 如果K等于2^n * 3^m * 5^o，需要测试
: 的序列一点也不少。
【在 h***i 的大作中提到】
: 对，求gcd倒是O(n), 但是gcd的因子太多了， 如果K等于2^n * 3^m * 5^o，需要测试
: 的序列一点也不少。
h*i
40 楼
我说的是总共n，不是nlgn，gcd已经被证明过了，最多recursion 5次。可以当常数。
【在 A***o 的大作中提到】
: gcd can be done in O(logn)
【在 A***o 的大作中提到】
: gcd can be done in O(logn)
相关阅读
加微信48173697进入全球华人私密约炮交友平台。遇到了超级小气的领导，要不要走呢？进了狗家，还刷题吗？谁说我没工作？ (转载)老板就只会画大饼，你每天加班为的是什么？Amazon AWS组用的大概是什么tech stack?口头答应了offer还可以谈sign on吗？西雅图computer vision scientist职位 (转载)【2019年2月20日 334 个股票的短期谷底高峰预测】 (转载)三番保安都刷题转码了网上内推有用吗？【工作机会】南京大学惠普三农金融科技研究中心诚招助理研究员 （博士后级别）问个另类的，半导体设备转EE-求建议纽约职场“潜规则”白人少女性多老中的世界里只有Pip和刷题办公室恋情，就真的“该死”吗？见过裁员，没见过这么开心的OPT邮寄到后多久他们会cash out 支票??公司上市或者被收购的可能性多大？换工作的选择 (转载)