d**********x
发帖数: 4083 | 1 一般还是能想到 str+str 然后kmp或者hash的吧
利用周期性确实太巧妙了。 |
|
p******9
发帖数: 47 | 2 相当于找这个字符串的最小循环节的长度，求出kmp算法的next数组，假设字符串长度
为N，最小循环节的长度是 N - next[N] 同时要求 N % (N - next[N]) == 0 |
|
m******s
发帖数: 165 | 3 好像最近只见过一道用kmp来dp的。。。srm 557 div 2 1000 |
|
p*****2
发帖数: 21240 | 4
多谢大牛。有时间得练练kmp了。看了一下感觉还挺麻烦的。 |
|
x********y
发帖数: 14 | 5 不重复的单词个数是 最小周期数。
然后每个不重复单词出现的次数是一样的。根据这两个推论，可以直接append
original str， 然后kmp查找最先出现的次数找到最小周期 |
|
H****s
发帖数: 247 | 6 对， 除非用rolling hash 或 KMP 否则就是O(N^2). 上个班的功夫怎么就这么多回帖
啦，慢慢看吧。 |
|
c********t
发帖数: 5706 | 7 嗯，还是不行，看来每个字母都要从头比较，还是要N^2算法才行。
KMP感觉在这道题不好用。 |
|
p*****2
发帖数: 21240 | 8
substring O(n)
这题rolling hash, 不过要选mod的话，我就没有经验了。不知道应该怎么选择好。
再有就是KMP。mshearts说的。 |
|
d**********x
发帖数: 4083 | 9 一般还是能想到 str+str 然后kmp或者hash的吧
利用周期性确实太巧妙了。 |
|
p******9
发帖数: 47 | 10 相当于找这个字符串的最小循环节的长度，求出kmp算法的next数组，假设字符串长度
为N，最小循环节的长度是 N - next[N] 同时要求 N % (N - next[N]) == 0 |
|
p*****2
发帖数: 21240 | 11
多谢大牛。有时间得练练kmp了。看了一下感觉还挺麻烦的。 |
|
x********y
发帖数: 14 | 12 不重复的单词个数是 最小周期数。
然后每个不重复单词出现的次数是一样的。根据这两个推论，可以直接append
original str， 然后kmp查找最先出现的次数找到最小周期 |
|
H****s
发帖数: 247 | 13 对， 除非用rolling hash 或 KMP 否则就是O(N^2). 上个班的功夫怎么就这么多回帖
啦，慢慢看吧。 |
|
c********t
发帖数: 5706 | 14 嗯，还是不行，看来每个字母都要从头比较，还是要N^2算法才行。
KMP感觉在这道题不好用。 |
|
p*****2
发帖数: 21240 | 15
看来还是得搞KMP呀。我这个周末得好好学学。 |
|
c********t
发帖数: 5706 | 16 算出周期，length再一除，不也一样？
如何算周期，看我那个另外一个帖子的最后回帖。
KMP不是 O(n), 把所有length都试一遍，不还是O(n^2)? |
|
l****i
发帖数: 2772 | 17 在S1里找到S2的第一次出现，用KMP是O(n) |
|
p*****2
发帖数: 21240 | 18
你那个帖子的回帖不是O(n)吧？KMP为什么不是O(n)? |
|
c********t
发帖数: 5706 | 19 KMP搜s是O(n), 问题是这道题，你难道不要试 从length 1到n/2的所有substring吗？ |
|
l****i
发帖数: 2772 | 20 用KMP其实也是找到你所说的周期，然后用length去除。 |
|
l****i
发帖数: 2772 | 21 为什么O(n^2)？KMP去找，是O（n）啊。 |
|
c********t
发帖数: 5706 | 22 我也有点懵了。
给你一个string abaaabaa
你拿什么去kmp找周期？难道不是要拿a, ab, aba, abaa去找吗？O(n*n)啊 |
|
p*****2
发帖数: 21240 | 23
大牛。我刚才做了一个KMP，没发现比BF快呀。 |
|
|
p*****2
发帖数: 21240 | 25
原帖是我转的。不过这题我碰到也完了，因为从来没写过KMP。 |
|
p*****2
发帖数: 21240 | 26
我比较不爱看书。CLRS买了，看的不多。主要是碰到题目里有不会的算法再看。当然不
一定看CLRS了，也可能wiki或者其他的讲算法的文章。主要是得能看懂才行。慢慢积累
吧。今天才做了KMP。 |
|
c********t
发帖数: 5706 | 27 哈哈哈，我也看他不顺眼。
凡是要背的题，俺都不顺眼，俺记性不好。 |
|
|
|
|
|
|
p*****2
发帖数: 21240 | 33
刚做了把伪牛，用rolling hash做的，没快。不知道是不是leetcode的测试数据还是太
小了，体现不出来优势。 |
|
p*****2
发帖数: 21240 | 34 回头用CF试试效果。总是感觉应该有效果才对。不然那些竞赛题都BF就可以搞了？那是
不可能的。 |
|
|
|
|
|
p*****2
发帖数: 21240 | 39
感觉比KMP要简单呀。next[]是啥东西。 |
|
B********t
发帖数: 147 | 40 next[]就是那个记录不匹配时下一个开始匹配位置的数组。
和KMP那个不一样。。是我弄错了。。 |
|
|
j*****y
发帖数: 1071 | 42 确实用 kmp简单，和那个 storm8 的题目一样
pattern = S
source = S + S
找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
return
true, 否则 return false |
|
|
c********t
发帖数: 5706 | 44 就算知道解法，还必须知道并写对KMP，google面试果然比以前难了不少。 |
|
H****s
发帖数: 247 | 45 其实不用这么麻烦， 像二爷说的，kmp pi function 直接解决！ |
|
f****s
发帖数: 74 | 46 KMP 中的：
while(k>0) and P[k+1]!=P[q]
k=pi[k];
照着字符串画图，半天也没搞懂。
大侠给简明说一下吧？ |
|
|
d*********g
发帖数: 154 | 48
嗯应该是这样，如果是KMP的话就是O(n)了~ |
|
p*****2
发帖数: 21240 | 49
多谢大牛。你对interval tree, KMP,union find这些算法都练得很熟了吗？ |
|
p*****2
发帖数: 21240 | 50
多谢大牛。你对interval tree, KMP,union find这些算法都练得很熟了吗？ |
|
