p*****2
发帖数: 21240 | 1 擦，真心跪了，我找了HR要了test的结果，各位大牛看看吧，貌似我题目理解错了？
extreme_single_letter
single letter
0.25 s. WRONG ANSWER got 0 expected 1
extreme_a5
a*5
0.24 s. WRONG ANSWER got 0 expected 5
medium1
ab*1000
0.31 s. WRONG ANSWER got 1 expected 1000
好可惜。。这个教训好深刻
O(n)的解法。 |
l****i
发帖数: 2772 | 2 二爷，我告诉你吧，这个题不是之前帖子里那个意思！我今早做了，一激动提交了，结
果后悔了，忘了考虑worst case的复杂度。估计要跪了。 |
l****i
发帖数: 2772 | 3 正确题意:
按照string长度N，一共有N种shift.当i shift （0=
叫做cyclic automorphism。要求return一共有多少cyclic automorphism。
byebye 0 shift counter = 1
yebyeb 1 shift
ebyeby 2 shift
byebye 3 shift counter = 2
yebyeb 4 shift
ebyeby 5 shift
return counter;
可以用KMP去比较（s+s,s）。结果我早上傻了，用KMP把所有的s在s+s里找了一遍。。
。。提交了才发现，我跪了。其实只要找到第一个出现的重复出现的S的位置就够了。
比如byebye，第一次重复在位置3,用s的length去除第一次位置，就是结果。
所有a*5,其实是aaaaa，应该结果是5！ |
p*****2
发帖数: 21240 | 4
对。我这个帖子的题意就是这个意思。原帖的问题是错的。LZ纠正了，可是没人看了。
【在 l****i 的大作中提到】
: 正确题意:
: 按照string长度N，一共有N种shift.当i shift （0=: 叫做cyclic automorphism。要求return一共有多少cyclic automorphism。
: byebye 0 shift counter = 1
: yebyeb 1 shift
: ebyeby 2 shift
: byebye 3 shift counter = 2
: yebyeb 4 shift
: ebyeby 5 shift
: return counter;
|
p*****2
发帖数: 21240 | 5
看来还是得搞KMP呀。我这个周末得好好学学。
【在 l****i 的大作中提到】
: 正确题意:
: 按照string长度N，一共有N种shift.当i shift （0=: 叫做cyclic automorphism。要求return一共有多少cyclic automorphism。
: byebye 0 shift counter = 1
: yebyeb 1 shift
: ebyeby 2 shift
: byebye 3 shift counter = 2
: yebyeb 4 shift
: ebyeby 5 shift
: return counter;
|
c********t
发帖数: 5706 | 6 算出周期，length再一除，不也一样？
如何算周期，看我那个另外一个帖子的最后回帖。
KMP不是 O(n), 把所有length都试一遍，不还是O(n^2)?
【在 p*****2 的大作中提到】
: 擦，真心跪了，我找了HR要了test的结果，各位大牛看看吧，貌似我题目理解错了？
: extreme_single_letter
: single letter
: 0.25 s. WRONG ANSWER got 0 expected 1
: extreme_a5
: a*5
: 0.24 s. WRONG ANSWER got 0 expected 5
: medium1
: ab*1000
: 0.31 s. WRONG ANSWER got 1 expected 1000
|
l****i
发帖数: 2772 | 7 在S1里找到S2的第一次出现，用KMP是O(n)
【在 c********t 的大作中提到】
: 算出周期，length再一除，不也一样？
: 如何算周期，看我那个另外一个帖子的最后回帖。
: KMP不是 O(n), 把所有length都试一遍，不还是O(n^2)?
|
p*****2
发帖数: 21240 | 8
你那个帖子的回帖不是O(n)吧？KMP为什么不是O(n)?
【在 c********t 的大作中提到】
: 算出周期，length再一除，不也一样？
: 如何算周期，看我那个另外一个帖子的最后回帖。
: KMP不是 O(n), 把所有length都试一遍，不还是O(n^2)?
|
c********t
发帖数: 5706 | 9 KMP搜s是O(n), 问题是这道题，你难道不要试 从length 1到n/2的所有substring吗？
【在 p*****2 的大作中提到】
:
: 你那个帖子的回帖不是O(n)吧？KMP为什么不是O(n)?
|
l****i
发帖数: 2772 | 10 用KMP其实也是找到你所说的周期，然后用length去除。
【在 c********t 的大作中提到】
: KMP搜s是O(n), 问题是这道题，你难道不要试 从length 1到n/2的所有substring吗？
|
|
|
c********t
发帖数: 5706 | 11 对啊，所以还是O(n^2), 因为你要从1试到n/2看有没有周期啊，难道还有别的trick?
【在 l****i 的大作中提到】
: 用KMP其实也是找到你所说的周期，然后用length去除。
|
l****i
发帖数: 2772 | 12 为什么O(n^2)？KMP去找，是O（n）啊。
【在 c********t 的大作中提到】
: 对啊，所以还是O(n^2), 因为你要从1试到n/2看有没有周期啊，难道还有别的trick?
|
e******i
发帖数: 106 | 13 原帖楼主表示第一次做这种Online test 不看清题目狠丢人，教训狠深刻，吃亏狠深 |
l****i
发帖数: 2772 | 14 move on，我早上做的，也跪了。
【在 e******i 的大作中提到】
: 原帖楼主表示第一次做这种Online test 不看清题目狠丢人，教训狠深刻，吃亏狠深
|
c********t
发帖数: 5706 | 15 我也有点懵了。
给你一个string abaaabaa
你拿什么去kmp找周期？难道不是要拿a, ab, aba, abaa去找吗？O(n*n)啊
【在 l****i 的大作中提到】
: 为什么O(n^2)？KMP去找，是O（n）啊。
|
l****i
发帖数: 2772 | 16 我的意思是，比如这题输入是"abab"
KMP("abababab","abab")，从index位置1开始找，可以找到index位置2，发现找到了。
这样KMP找到index是2.这个2就是你所说的周期吧。
【在 c********t 的大作中提到】
: 我也有点懵了。
: 给你一个string abaaabaa
: 你拿什么去kmp找周期？难道不是要拿a, ab, aba, abaa去找吗？O(n*n)啊
|
c********t
发帖数: 5706 | 17 哦，对，明白了，多谢。
【在 l****i 的大作中提到】
: 我的意思是，比如这题输入是"abab"
: KMP("abababab","abab")，从index位置1开始找，可以找到index位置2，发现找到了。
: 这样KMP找到index是2.这个2就是你所说的周期吧。
|
p****e
发帖数: 3548 | 18 这个问题，简化一下就是求一个矩阵的秩
矩阵是字符串的数值 |
p*****2
发帖数: 21240 | 19 找到这题的出处了。还没看太懂。
A typical problem seen quite often is: given a string find its shortest
substring, such that the concatenation of one or more copies of it results
in the original string. Again the problem can be reduced to the properties
of the failure function. Let's consider the string
A B A B A B
and all its proper suffix/prefixes in descending order:
1 A B A B
2 A B
3 /the empty string/
Every such suffix/prefix uniquely defines a string, which after being "
inserted" in front of the given suffix/prefix gives the initial string. In
our case:
1 A B
2 A B A B
3 A B A B A B
Every such "augmenting" string is a potential "candidate" for a string, the
concatenation of several copies of which results in the initial string. This
follows from the fact that it is not only a prefix of the initial string
but also a prefix of the suffix/prefix it "augments". But that means that
now the suffix/prefix contains at least two copies of the "augmenting"
string as a prefix (since it's also a prefix of the initial string) and so
on. Of course if the suffix/prefix under question is long enough. In other
words, the length of a successful "candidate" must divide with no remainder
the length of the initial string.
So all we have to do in order to solve the given problem is to iterate
through all proper suffixes/prefixes of the initial string in descending
order. This is just what the "failure function" is designed for. We iterate
until we find an "augmenting" string of the desired length (its length
divides with no remainder the length of the initial string) or get to the
empty string, in which case the "augmenting" string that meets the above
requirement will be the initial string itself. |
p*****2
发帖数: 21240 | 20
大牛。我刚才做了一个KMP，没发现比BF快呀。
【在 l****i 的大作中提到】
: 正确题意:
: 按照string长度N，一共有N种shift.当i shift （0=: 叫做cyclic automorphism。要求return一共有多少cyclic automorphism。
: byebye 0 shift counter = 1
: yebyeb 1 shift
: ebyeby 2 shift
: byebye 3 shift counter = 2
: yebyeb 4 shift
: ebyeby 5 shift
: return counter;
|
|
|
l*********8
发帖数: 4642 | 21 storm8 是自己去他家网上投，然后就会收到online test的链接吗？ 还是需要人refer?
【在 p*****2 的大作中提到】
: 擦，真心跪了，我找了HR要了test的结果，各位大牛看看吧，貌似我题目理解错了？
: extreme_single_letter
: single letter
: 0.25 s. WRONG ANSWER got 0 expected 1
: extreme_a5
: a*5
: 0.24 s. WRONG ANSWER got 0 expected 5
: medium1
: ab*1000
: 0.31 s. WRONG ANSWER got 1 expected 1000
|
p*****2
发帖数: 21240 | 22
refer?
我也不知道呀。估计都可以吧。
【在 l*********8 的大作中提到】
: storm8 是自己去他家网上投，然后就会收到online test的链接吗？ 还是需要人refer?
|
i**********e
发帖数: 1145 | |
s***y
发帖数: 203 | |
c********t
发帖数: 5706 | 25 是的。除了KMP, 还有啥好方法？
【在 i**********e 的大作中提到】
: 你们讨论的什么题，是这道吗？
: http://discuss.leetcode.com/questions/1014/cyclic-rotation
|
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 27 算了，自己动手丰衣足食，写了一个
def maxsub(s:String):Int={
val n=s.length
val dp=new Array[Int](n)
for(i<-1 until n){
var j=i
while(j>0 && s(i)!=s(dp(j-1))) j=dp(j-1)
dp(i)=if(j>0) dp(j-1)+1 else 0
}
var j=dp(n-1)
while(n%(n-j)!=0) j=dp(j-1)
n/(n-j)
} |
p*****2
发帖数: 21240 | |
j*******e
发帖数: 1058 | |
p*****2
发帖数: 21240 | 30
原帖是我转的。不过这题我碰到也完了，因为从来没写过KMP。
【在 j*******e 的大作中提到】
: 2爷都要跪了，我等草码，不要碎了。。。
|
