B********t
发帖数: 147 | 1 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
。。 |
f*****e
发帖数: 2992 | 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
发帖数: 1071 | 3 先算两个长度 |S| 和 |T| ,算出 K = |S| / |T|
再把 T复制 K 次， 和 S 比较 ?
O(|S| + |T|)
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
|
j*****y
发帖数: 1071 | 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;
|
B********t
发帖数: 147 | 5 T是未知的。。
【在 j*****y 的大作中提到】
: 先算两个长度 |S| 和 |T| ,算出 K = |S| / |T|
: 再把 T复制 K 次， 和 S 比较 ?
: O(|S| + |T|)
|
s*********l
发帖数: 103 | 6
suffix tree
http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
|
f*****e
发帖数: 2992 | 7 S是T=S复制1次的结果:-)
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
|
B********t
发帖数: 147 | 8 @。@ ！@#￥%……&＊（）
【在 f*****e 的大作中提到】
: S是T=S复制1次的结果:-)
|
A***o
发帖数: 358 | |
B********t
发帖数: 147 | |
|
|
l*********8
发帖数: 4642 | 11 设字符串S长度为N。
取K为N的质数因子，然后求解。 |
p*****2
发帖数: 21240 | |
j*****y
发帖数: 1071 | 13 确实用 kmp简单，和那个 storm8 的题目一样
pattern = S
source = S + S
找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
return
true, 否则 return false
【在 p*****2 的大作中提到】
: KMP吧。
|
f*****e
发帖数: 2992 | 14 你题目都没说明白，一点严谨性都没有，很奇怪这么多人re你的贴。
【在 B********t 的大作中提到】
: 好像是这么回事。
|
B********t
发帖数: 147 | 15 ...........好吧....我的错. 向来语文不好 您也不要这么大火气。
【在 f*****e 的大作中提到】
: 你题目都没说明白，一点严谨性都没有，很奇怪这么多人re你的贴。
|
p*****p
发帖数: 379 | 16 ababa是aba复制1次的结果还是2次的结果？
还是说复制aba得不到ababa
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
|
P*******b
发帖数: 1001 | 17 我咋觉得两个pointer不停移就搞定了呢
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
|
B********t
发帖数: 147 | 18 懂了。。知道2爷的意思了。。我太挫了
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
|
l*******b
发帖数: 2586 | 19 nice solution indeed !
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
|
j*****y
发帖数: 1071 | 20 kmp 可以达到线性，你这个能线性？
【在 P*******b 的大作中提到】
: 我咋觉得两个pointer不停移就搞定了呢
|
|
|
p*****2
发帖数: 21240 | |
P*******b
发帖数: 1001 | 22 O(2N)阿
【在 j*****y 的大作中提到】
: kmp 可以达到线性，你这个能线性？
|
Y**Y
发帖数: 66 | 23 先算S长度n, 然后找出n所有大于1的质因子数
然后对任何一个质因子K，判断S是不是K个相同的字符串组成的。
复杂度应该接近linear,因为一个数的质因子数很少。
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
|
A***o
发帖数: 358 | 24 不行吧，整数分解，complexity class都不定
【在 Y**Y 的大作中提到】
: 先算S长度n, 然后找出n所有大于1的质因子数
: 然后对任何一个质因子K，判断S是不是K个相同的字符串组成的。
: 复杂度应该接近linear,因为一个数的质因子数很少。
|
l*******b
发帖数: 2586 | 25 那是因为那个复杂度是按number of digits定义的,哈哈...
【在 A***o 的大作中提到】
: 不行吧，整数分解，complexity class都不定
|
l*********8
发帖数: 4642 | 26 握手
【在 Y**Y 的大作中提到】
: 先算S长度n, 然后找出n所有大于1的质因子数
: 然后对任何一个质因子K，判断S是不是K个相同的字符串组成的。
: 复杂度应该接近linear,因为一个数的质因子数很少。
|
c********t
发帖数: 5706 | 27 就算知道解法，还必须知道并写对KMP，google面试果然比以前难了不少。
【在 B********t 的大作中提到】
: 给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。不要n^2的解
: 。。
|
s*******i
发帖数: 7 | |
j*****y
发帖数: 1071 | 29 楼主面试官是老中吗？
【在 s*******i 的大作中提到】
: http://poj.org/problem?id=2406
|
B********t
发帖数: 147 | 30 是我同学面的题。他说听声不像。哈哈。
【在 j*****y 的大作中提到】
: 楼主面试官是老中吗？
|
|
|
r*********n
发帖数: 4553 | 31 用suffix array应该可以做，但是提升也不大，因为要sort，所以是O(nlogn) |
r*********n
发帖数: 4553 | 32 题目不是这个意思吧
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
|
f******t
发帖数: 18 | 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的正解差不多？ |
a***o
发帖数: 1182 | 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))
|
b*****u
发帖数: 648 | 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))
|
C*******n
发帖数: 24 | 36 同意，例如aabbaabb，gcd是4，k是2
【在 b*****u 的大作中提到】
: 应该k是gcd的因子吧
|
h***i
发帖数: 1970 | 37 对，求gcd倒是O(n), 但是gcd的因子太多了， 如果K等于2^n * 3^m * 5^o，需要测试
的序列一点也不少。
【在 b*****u 的大作中提到】
: 应该k是gcd的因子吧
|
H****s
发帖数: 247 | 38 其实不用这么麻烦， 像二爷说的，kmp pi function 直接解决！
【在 j*****y 的大作中提到】
: 确实用 kmp简单，和那个 storm8 的题目一样
: pattern = S
: source = S + S
: 找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
: return
: true, 否则 return false
|
A***o
发帖数: 358 | 39 gcd can be done in O(logn)
【在 h***i 的大作中提到】
: 对，求gcd倒是O(n), 但是gcd的因子太多了， 如果K等于2^n * 3^m * 5^o，需要测试
: 的序列一点也不少。
|
h***i
发帖数: 1970 | 40 我说的是总共n，不是nlgn，gcd已经被证明过了，最多recursion 5次。可以当常数。
【在 A***o 的大作中提到】
: gcd can be done in O(logn)
|
