由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 没看出来KMP快呀
相关主题
关于leetcode 的strStr这题Wildcard String Matching和怎么提高写程序能力的总结
为什么面试题目都答出来了还是跪了?还真从来没见过考KMP之类string matching算法的
只刷了110道现在。字串 查找的 最佳算法。
关于KMP, Manacher,Morris算法其实我很想知道, 多少软工能25分钟内把heapsort写下
bloomberg onsite & offer两道面试题,请大家说说看法
请问 KMP算法重要吗?akamai面经
这个题有什么好方法吗?弯曲中型IT公司面经
发个F onsite后的加试面经吧 求bless攒人品,twitter电话面经
相关话题的讨论汇总
话题: kmp话题: hash话题: boyer话题: bf话题: 顺眼
进入JobHunting版参与讨论
1 (共1页)
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
: ?

相关主题
请问 KMP算法重要吗?Wildcard String Matching和怎么提高写程序能力的总结
这个题有什么好方法吗?还真从来没见过考KMP之类string matching算法的
发个F onsite后的加试面经吧 求bless字串 查找的 最佳算法。
进入JobHunting版参与讨论
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
13
有些牛直接hash比较
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就可以搞了?那是
不可能的。
1 (共1页)
进入JobHunting版参与讨论
相关主题
攒人品,twitter电话面经bloomberg onsite & offer
老码农面Google的一点经验分享请问 KMP算法重要吗?
愤怒,amazon interviewer 不知KMP 算法这个题有什么好方法吗?
FB两次电面发个F onsite后的加试面经吧 求bless
关于leetcode 的strStr这题Wildcard String Matching和怎么提高写程序能力的总结
为什么面试题目都答出来了还是跪了?还真从来没见过考KMP之类string matching算法的
只刷了110道现在。字串 查找的 最佳算法。
关于KMP, Manacher,Morris算法其实我很想知道, 多少软工能25分钟内把heapsort写下
相关话题的讨论汇总
话题: kmp话题: hash话题: boyer话题: bf话题: 顺眼