h*********e
发帖数: 91 | 1 本来满简单的，一个hay_str.compare(i, needle_len, needle)就出来了。 我知道复
杂度比KMP 高，但是KMP记不住。 真的面试的时候，可不可以不用KMP， 就用一个
compare function阿？ |
|
b******g
发帖数: 3616 | 2 也看过不少KMP的讲解，觉得确实是matrix67讲得最清楚。CLRS讲得太生涩。之前刷lc
的strStr()这题是用土办法2 points做的，今天也跟风写了个KMP版的strStr()过了下
lc.
BTW: 今天才发现lc这题的interface改了，以前是返回指针，现在变成返回起始index
了。
vector KMPpreprocessing(char *needle) {
int m = strlen(needle);
// assume j = match[i]: needle[i-j:i] == needle[0:j]
vector match(m,-1);
int j = -1;
for(int i=1; i
while(j>=0 && needle[i]!=needle[j+1]) j = match[j];
if(needle[i]==needle[j+1]) j++;
... 阅读全帖 |
|
z*******y
发帖数: 578 | 3 我上个礼拜面Amazon的时候，问到了string matching的，找出一个string在另一个
string中出现的位置，我只稍微提了一下KMP，写程序的时候就用了最直接的 O(mn）的
方法，也没再要求我用KMP实现 |
|
h*****1
发帖数: 74 | 4 这是第三个phone interview。 前面两个说挺好。 上来就要写string match 的算法。
前两天自己刚写了个KMP算法，但没有test。所以直接念给他听。这老几首先问我为什
么函数名前要加KMP。我说是个O(m+n)的算法。完了问我为什么要next函数。 接着要我
test, 用 hongkong， kong 两个串。不work， 就说要fail掉我。我无语。他说太复杂
。我说我能保证两点，一，能编译通过，二，算法本身logic是正确的。由于算法本身
复杂，需要debug才work， 我说我可以电话完了后email给他work的code。 他说不需要。
争他妈愤怒。 已经follow了一个月， 很轻易的就fail掉。能有地方抱怨一下吗。找个
工作真不容易。唉。 |
|
g*********s
发帖数: 1782 | 5 frankly speaking, i don't think anyone can easily write a bug free kmp in 20
min, unless he's a super bull or he has the existing code in hands.
obviously, your strategy is not very good. u want to impress him. but
obviously he doesn't think u r a super bull.
next time in such situation, just gives the naive algorithm first. give kmp
only when they ask improvement.
要。 |
|
h*****1
发帖数: 74 | 6 you are absolutely right。 说实在的，我并不是想impress他， 而是直接就想当然
是KMP。
20
kmp |
|
h*****1
发帖数: 74 | 7 我的感觉是这老几压根就不知道KMP。总问为什么函数名以kmp开始。kmp_next是干什么
用的。 |
|
g**e
发帖数: 6127 | 8 Here is my java version
public static void KMP(String target, String pattern) {
boolean found = false;
int[] overlap = getOverlap(pattern);
int j = 0;
for (int i=0; i
while (true) {
if (target.charAt(i) == pattern.charAt(j)) {
j++;
if (j =... 阅读全帖 |
|
|
p*****2
发帖数: 21240 | 10
那OJ咋办呢？比如storm8那个题，用KMP不快的话，BF过不了，KMP也不一定能过呀。 |
|
f*****e
发帖数: 2992 | 11 Boyer-More似乎比KMP更快，KMP每个letter都得比较一遍，Boyer-More一看后边不对劲
，前边就不比较了，所以可以节省比较次数。不过这些方法实际都不咋地，最猛的要看
最新的文献。 |
|
p*****2
发帖数: 21240 | 12
那topcoder的题用KMP怎么就可以解呢？难道专为为了KMP过，BF过不了设计test cases
？ |
|
m******s
发帖数: 165 | 13 KMP本身不快，特别对于随机串，实践中往往使用Sunday、BM等算法。。。
有些竞赛题用KMP不是用来完全匹配的，而是用那个前缀函数，因为其计算就意味着建
立了一个自动机。
cases |
|
r*********n
发帖数: 4553 | 14 BM也可以像KMP那样子用DFA优化吧，这样子理论和实际都比KMP快。
另外也可以RK算法 O(N)。面试让我选，我选RK，coding起来更简单。 |
|
c***0
发帖数: 449 | 15 你直接回到0也可以，只是效率差一些，第二部是利用以前的计算结果，快速找到接下
来该和谁再比。你可以理解为计算Kmp的表格的时候也是kmp算法。 |
|
w****3
发帖数: 110 | 16 新手，看了一整天KMP算法，还是没有搞得很清楚。希望大牛给讲讲。
假设一个pattern string p， KMP的第一步是用pattern生成一个next array。根据这
个博客里讲的
http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.h
根据定义next[0]=-1，假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]
1)若P[j]==P[k]，则有P[0..k]==P[j-k,j]，很显然，next[j+1]=next[j]+1=k+1;
2)若P[j]!=P[k]，则可以把其看做模式匹配的问题，即匹配失败的时候，k值如何移
动，显然k=next[k]。
void getNext(char *p,int *next)
{
int j,k;
next[0]=-1;
j=0;
k=-1;
while(j
{
if(k==-1||p[j]==p[k]) //匹配的情况下,p[j]... 阅读全帖 |
|
r*****s
发帖数: 1815 | 17 Manacher并不是一个通用的算法，除了求回文。。你还用它干啥。。。它的功能可以用
后缀树或者后缀数组来代替。所以我没仔细研究过。
KMP的预处理是对pattern中的每个i，找到0-i范围内的等于后缀的最大前缀长度（利用
0-i-1范围内已经求得的结论进行"动态规划")，此数组记录为P[]
在pattern和实际字符串比较失配的时候，设pattern失配位置为i，则0-i-1范围内把等
于后缀的最大前缀移动到后缀位置，即从P[i - 1] 1 位置开始继续比较，若再次失
配，则重复。
KMP算法的思想是很清晰的。 |
|
r*****s
发帖数: 1815 | 18 为了证明不是胡吹大气附上一个刚写的strstr:
https://gist.github.com/anonymous/a949d6a76f6a72432cfc2c3045e5fb4d
: Manacher并不是一个通用的算法，除了求回文。。你还用它干啥。。。它的功能
可以用
: 后缀树或者后缀数组来代替。所以我没仔细研究过。
: KMP的预处理是对pattern中的每个i，找到0-i范围内的等于后缀的最大前缀长度
（利用
: 0-i-1范围内已经求得的结论进行"动态规划")，此数组记录为P[]
: 在pattern和实际字符串比较失配的时候，设pattern失配位置为i，则0-i-1范围
内把等
: 于后缀的最大前缀移动到后缀位置，即从P[i - 1] 1 位置开始继续比较，若
再次失
: 配，则重复。
: KMP算法的思想是很清晰的。
|
|
z*********n
发帖数: 1451 | 19
KMP其实不难，理解next数组含义就好。我写过支持通配符?和*的KMP...
Manacher确实没用，面试敢考你投诉他
Morris非常trivial啊，虽然后序比较复杂以外。
btw，以上三个基本100%肯定面试不会让你写代码，你可以提一句表示你知道有这么回
事，展现了你的知识面即可。 |
|
r*****s
发帖数: 1815 | 20 那我下次有人来onsite就考kmp
: 九章第一节就说了，写strstr不要写kmp，贪心法不考。
: 面试官看不懂，我特意没学。
|
|
发帖数: 1 | 21 There are two ways for KMP problem: one is by using finite definite
automation; the other is to use a shift.
Spent a couple of hours on them, still don't quite understand the way to
construct the dfa tables, any experts? |
|
w******k
发帖数: 917 | 22 网上见过这么多考题
还真没见过KMP, BM之类的string matching算法的
suffix tree就更不用说了
有谁见过考得么？ |
|
g*******y
发帖数: 1930 | 23 主要是不好写，后缀树就不说了，KMP BM虽然是可以能在面试时间内写出来，但是比起
其他普通的面试题要复杂很多，还不容易写正确，尤其如果你没怎么认真复习过。再说
了，既然是现成的算法，也考察不到candidate的思路等方面了。 |
|
g*******y
发帖数: 1930 | 24 Google一下吧，记不住名称，据说比KMP更好 |
|
y*******g
发帖数: 6599 | 25 KMP是太复杂了点
你要是不准备也很难现场写出来吧 |
|
g*********s
发帖数: 1782 | 26 oh, even worse, your code is not bug free.
20
kmp |
|
g*********s
发帖数: 1782 | 27 that means it's one algorithm level bug...
it's impressive to implement kmp. just get even better prepared next time by implement it clean. |
|
g**e
发帖数: 6127 | 28 this does not look right. you should calculate KMP automata and saved in an
array first. then keep looking up for next char. Not call kmp_next every
time. |
|
|
d**f
发帖数: 264 | 30 面试就是投interviewer所好，很可能他自己都搞不懂KMP |
|
h*****1
发帖数: 74 | 31 愿听其详。
其实我的KMP算法中next函数写错了。这会导致O(mn)的复杂度。但让一个人电话里写这
么多代码，是不是也有病！ |
|
g******0
发帖数: 221 | 32 羞愧的问， what does KMP stand for? |
|
g******0
发帖数: 221 | 33 安慰安慰。
请问，what does KMP stand for? What is it? 谢谢。
要。 |
|
p*********a
发帖数: 61 | 34 一味做题为导向，就是这个结果
实际工作中，一个简单、明了、好维护的代码，比一些奇怪的技巧更重要
而且，实际的问题几乎都不可能简单划归为所谓经典的算法
知不知道 kmp 并没有这么重要。
面试搞这些教科书上的问题，也是不得已而为之。主要还是看你的基本编程能力
面试还是先写一个直观和正确的代码。
至于优化，有些人关心，有些人不关心。
实际系统中关键的优化，有的是 senior 的人的关心, 多半也轮不到 junior 插手
而如果不是关键问题的话，把 O(n^2) 降到了 O(n) 又有什么关系呢
要。 |
|
h*****1
发帖数: 74 | 35 我要是知道写个naive的代码就可以了，怎会伤那脑筋写KMP
问题是，你若不做题。随便给你一个面试题你也做不出来， 不管你有多少年工作经验。 |
|
g******0
发帖数: 221 | 36 深有同感。刚才看到KMP detail，才想起来我n年前在课堂上学的, 不然怎么都记不得
。这东西，一般是学string algorithm才会记在心上的（或者是牛人）。确实有拼命做
题的感觉。
但还是祝lz好运。我下个星期也面amazon.还要飞过去。之前都没个点面什么的。从现
在的准备状态来看，和各位点评interview题目的水平一比，觉得自己会很惨。 |
|
l*y
发帖数: 21010 | 37 你可以换一个别的算法啊
KMP在实际应用中本来就不如boyer-moore算法
人家可能只接触过后者
要。 |
|
|
p*****2
发帖数: 21240 | 39 leetcode strStr, KMP跟暴力时间差不多呀。一点也看不出来快呀。怎么回事？ |
|
|
p*****2
发帖数: 21240 | 41
可是OJ的时候如果KMP不快的话，怎么通过呢？ |
|
|
i******r
发帖数: 793 | 43 kmp理论上复杂度低点，但是实际应用的效果没有那么好 |
|
f*****e
发帖数: 2992 | 44 KMP能过的Boyer-Moure肯定也行。
cases |
|
i******r
发帖数: 793 | 45 最近看了一些字符串hash函数
感觉很多情况下用hash可能比kmp啥的快多了 |
|
d*k
发帖数: 207 | 46 除非诚心做的数据，KMP和暴力算法的效率差不多。 |
|
c*****9
发帖数: 4247 | 47 因为写起来太复杂了？
那 kmp 还需要复习吗？ |
|
l****i
发帖数: 2772 | 48 要，现在的公司，问的越来越变态。看懂算法的话，KMP写起来不难。 |
|
s*****n
发帖数: 5488 | 49 几句话可以说清楚。
1.kmp算法有strstr变化而来。一旦不匹配，不是推到头，而是吧pattern推到另外一个
next array指示的位置,重新开始比较。
2.next array和pattern错开一位匹配而来，一旦开始匹配，顺序++,一旦不匹配，清零
重来。
例如：
ababaca
0012301
其实主要靠的逻辑和编码能力。 |
|
