p*****2 发帖数: 21240 | 1 leetcode strStr, KMP跟暴力时间差不多呀。一点也看不出来快呀。怎么回事? |
w****x 发帖数: 2483 | 2
KMP本来就没什么意思
【在 p*****2 的大作中提到】 : leetcode strStr, KMP跟暴力时间差不多呀。一点也看不出来快呀。怎么回事?
|
p*****2 发帖数: 21240 | 3
可是OJ的时候如果KMP不快的话,怎么通过呢?
【在 w****x 的大作中提到】 : : KMP本来就没什么意思
|
w****x 发帖数: 2483 | 4
早看KMP不顺眼了....
【在 p*****2 的大作中提到】 : : 可是OJ的时候如果KMP不快的话,怎么通过呢?
|
i******r 发帖数: 793 | 5 kmp理论上复杂度低点,但是实际应用的效果没有那么好 |
p*****2 发帖数: 21240 | 6
那OJ咋办呢?比如storm8那个题,用KMP不快的话,BF过不了,KMP也不一定能过呀。
【在 i******r 的大作中提到】 : kmp理论上复杂度低点,但是实际应用的效果没有那么好
|
f*****e 发帖数: 2992 | 7 Boyer-More似乎比KMP更快,KMP每个letter都得比较一遍,Boyer-More一看后边不对劲
,前边就不比较了,所以可以节省比较次数。不过这些方法实际都不咋地,最猛的要看
最新的文献。
【在 i******r 的大作中提到】 : kmp理论上复杂度低点,但是实际应用的效果没有那么好
|
c********t 发帖数: 5706 | 8 哈哈哈,我也看他不顺眼。
凡是要背的题,俺都不顺眼,俺记性不好。
【在 w****x 的大作中提到】 : : 早看KMP不顺眼了....
|
p*****2 发帖数: 21240 | 9
那topcoder的题用KMP怎么就可以解呢?难道专为为了KMP过,BF过不了设计test cases
?
【在 f*****e 的大作中提到】 : Boyer-More似乎比KMP更快,KMP每个letter都得比较一遍,Boyer-More一看后边不对劲 : ,前边就不比较了,所以可以节省比较次数。不过这些方法实际都不咋地,最猛的要看 : 最新的文献。
|
f*****e 发帖数: 2992 | 10 KMP能过的Boyer-Moure肯定也行。
cases
【在 p*****2 的大作中提到】 : : 那topcoder的题用KMP怎么就可以解呢?难道专为为了KMP过,BF过不了设计test cases : ?
|
|
|
m******s 发帖数: 165 | 11 KMP本身不快,特别对于随机串,实践中往往使用Sunday、BM等算法。。。
有些竞赛题用KMP不是用来完全匹配的,而是用那个前缀函数,因为其计算就意味着建
立了一个自动机。
cases
【在 p*****2 的大作中提到】 : : 那topcoder的题用KMP怎么就可以解呢?难道专为为了KMP过,BF过不了设计test cases : ?
|
p*****2 发帖数: 21240 | 12
大牛说的很好。确实是这样。有时间帮我看一下这道题吧。自动机是如何建立的?如果
通过自动机解决这个问题。我还没太看明白。
http://www.mitbbs.com/article_t/JobHunting/32327771.html
【在 m******s 的大作中提到】 : KMP本身不快,特别对于随机串,实践中往往使用Sunday、BM等算法。。。 : 有些竞赛题用KMP不是用来完全匹配的,而是用那个前缀函数,因为其计算就意味着建 : 立了一个自动机。 : : cases
|
l***i 发帖数: 1309 | |
l*****a 发帖数: 14598 | 14 我队你的每张图片都不太顺眼
【在 w****x 的大作中提到】 : : 早看KMP不顺眼了....
|
h******s 发帖数: 86 | 15 汤MM那张还不错。
【在 l*****a 的大作中提到】 : 我队你的每张图片都不太顺眼
|
i******r 发帖数: 793 | 16 最近看了一些字符串hash函数
感觉很多情况下用hash可能比kmp啥的快多了 |
p*****2 发帖数: 21240 | 17
应该是呀。hash一般怎么取mod呢?
【在 i******r 的大作中提到】 : 最近看了一些字符串hash函数 : 感觉很多情况下用hash可能比kmp啥的快多了
|
p*****2 发帖数: 21240 | 18
刚做了把伪牛,用rolling hash做的,没快。不知道是不是leetcode的测试数据还是太
小了,体现不出来优势。
【在 l***i 的大作中提到】 : 有些牛直接hash比较
|
p*****2 发帖数: 21240 | 19 回头用CF试试效果。总是感觉应该有效果才对。不然那些竞赛题都BF就可以搞了?那是
不可能的。 |