x*********w
发帖数: 533 | 1 以前一直以为KMP算法很复杂，现场写几乎不可能，所以一直有畏惧心理。
今天看CLRS那一大堆符号证明推理啥的直接跳过去，盯着见匹配数组的伪代码看，就那
么3，4行关键的，慢慢能弄清楚怎么回事。CLRS上怎么能写那么复杂，直接把人吓回去
了。 |
|
P***t
发帖数: 1006 | 2 有面试考KMP的吗? 这种人有没扪心自问能不能自己发明这个算法呢? |
|
z*********8
发帖数: 2070 | 3 BM不行吗？快几倍
Sunday不行吗？ 比BM还快。 不要和我说worst case 是N*M， 实际中可能吗？
难道面试官指定要KMP? |
|
g**G
发帖数: 767 | 4 kmp每次都记不住，还是用rabin karp吧 |
|
|
|
r********d
发帖数: 7742 | 7 最帅的还是KMP。
当初领会了这个算法的时候，爽得好像在玩游戏时，发现了定位打boss的方法。 |
|
h****p
发帖数: 87 | 8 研究下KMP算法，看到wiki上的解释有一点不是很理解 请大牛帮忙解释解释
算table如下：
algorithm kmp_table:
input:
an array of characters, W (the word to be analyzed)
an array of integers, T (the table to be filled)
output:
nothing (but during operation, it populates the table)
define variables:
an integer, pos ← 2 (the current position we are computing in T)
an integer, cnd ← 0 (the zero-based index in W of the next
character of the current candidate substring)
(the first few v... 阅读全帖 |
|
|
A*********c
发帖数: 430 | 10 碰上这题，花5分钟列个表，把几个常见算法如bruteforce，KMP，Rabin，Boyer Moore
复杂度都分析一下，优劣大概一说。然后让面试官挑一个你bug free写出来，这轮我觉
得就没跑了。 |
|
|
i***u
发帖数: 89 | 12 http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-a
上面链接中的len = lps[len-1]; 怎么证明 为什么不是len = len -1, 因为lps[len-1
]是前面那个子串的lps最大长度，而不是整个当前子串的
例如 ABAD___ABAA ,当A与D 不match的时候 我们直接去看ABAD中的B而不是A ， 怎么
证明不存在可能性：ABA match
BAA, 我知道由于前面的ABAD与ABAA不能match导致了这种结果 可以忽略ABA 直接看ABA
中得最长lps， 即AB,因为ABA的lps是1, 但是我无法证明这个东西一定成立 不知道大
家怎么理解的？ |
|
w********0
发帖数: 377 | 13 大牛们能否给介绍介绍kmp。看了好几个版本的讲解，都还不是很清楚。到底那个表是
按照什么rule建立起来的。看着逻辑很混乱。有没有大牛能给他简单易懂的版本。或者
给推荐一个比较好的链接。
万分感谢！！！ |
|
w********0
发帖数: 377 | 14 谢谢。topcoder上的看了，只能明白前面那个RK， 后面的kmp还是有点晕。
我看看这个。谢谢了 |
|
x**********a
发帖数: 1372 | 15 面试的时候曾经有人问过我kmp，我说了一下大概思想，就是不用回头从i+1开始重新
compare，但是具体不记得了，需要查一下资料brush up一下。
对方也给了我offer，没有任何不悦。但是那是三年前的行情了。
所以我觉得不需要准备这个。 |
|
z******g
发帖数: 271 | 16 大概说一下我的理解吧：
kmp本质上就是一个state machine：你维护一个state来记录当前匹配的字符数，假设
这个state名为match。每读入一个新字符，match就会发生变化：match = transition(
match, str[i])。当match等于pattern的长度时或字符用完时，算法就结束了。可以把
这个算法想象成吃豆人，只吃不吐。
具体的实现我见过两种，一种是deterministic，可以真正做到只吃不吐；另一种是non
-deterministic，有时候得吐一个。一般大家说的都是第二种，其实第一种更好理解。
deterministic版本中，transition表是一个大小为mn的table，这里m为pattern的长度
，n为输入charset的大小（例如小写字母就是26）。叫deterministic的原因是它可以
真正做到match = transition(match, str[i])，所以可以一直前进。缺点是建表开销
大。这个版本在红书里有讲解。
non-deterministic版本就是平时大家说的建partial match t... 阅读全帖 |
|
|
a********r
发帖数: 76 | 18 感觉最晕是KMP的下标，不知道除了死记硬背有没有别的办法 |
|
发帖数: 1 | 19 九章第一节就说了，写strstr不要写kmp，贪心法不考。
面试官看不懂，我特意没学。 |
|
r*****s
发帖数: 1815 | 20 这样，下次有人来onsite，我先给他讲一遍KMP，再让他写
: 坚决不学，估计这种题都是留给那些简历上面写参加过竞赛的人
|
|
r*****s
发帖数: 1815 | 21 不会KMP怎么知道刷哪个盘子啊！
: 刷盘子也要on-site过才让刷？
|
|
|
G******i
发帖数: 5226 | 23 ☆─────────────────────────────────────☆
viisa (viiiiiisa) 于 (Fri Dec 23 01:33:02 2011, 美东) 提到:
之前都不知道还有如此方便的网站，
随便在上面做了几道题目，竟然有很不错的公司主动联系我给电面，比 refer 效率高
多了。做5道题目就可以申Facebook, Dropbox 等公司了
下月6号还有个比赛 http://codesprint.interviewstreet.com/recruit/challenges/
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Fri Dec 23 01:39:55 2011, 美东) 提到:
啥公司？
☆─────────────────────────────────────☆
viisa (viiiiiisa) 于 (Fri Dec 23 01:54:43 2011, 美东) 提到:
这里有列表，里面的一个自己感兴趣的公司
http://blog.inter... 阅读全帖 |
|
a*******n
发帖数: 112 | 24 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
吧。
- 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
一个链表。要求把它拍扁，顺序随意。
一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。
当然这个算法有更好的解，既然不要求顺序，而且有头尾指针，每次把父子链表接到尾
巴后面就可以了。连递归都省了。
- 算sqrt()
我提出用牛顿法，刚画完坐标系就说不让用。原话是“newton's method is for
mathematics, please use comput... 阅读全帖 |
|
f*******r
发帖数: 976 | 25 LZ不用多放在心上，这道题不简单啊。这道题考的是对KMP的理解深度，最主要的就是
考的KMP里面的计算pattern string的next矩阵的计算方法。如果一个string是由一个
substring重复多次拼接而成，那么它的next矩阵肯定是这样：
x x x 3 4 5 6 7 8 9 ...
也就是说，next矩阵的后半部分一定是一个递增的数列。通过这个next矩阵我们就可以
计算出那个substring的长度，然后再来计算整个数组是不是这个substring的倍数，比
如abcdabcdabc虽然是重复多次，但是最后那个重复是abc，没有完整，少了个d。对于
KMP的理解，这篇博文写得不错：http://blog.csdn.net/v_july_v/article/details/7041827
我也来贴两个解法，第一个解法是暴力解法，从左到右扫描，如果找到了那个重复的
substring，就用这个substring来继续match整个string。如果不成功，那么就继续找
那个substring，不回溯，只是比较次数多，时间复杂度不是O(n)，而是O(n^2).
// R... 阅读全帖 |
|
发帖数: 1 | 26 KMP在面试中没必要很好的掌握，知道个大概就行了。
别浪费那个时间写code，还是把有限的时间分配到更有意义的事上吧。
以下是原因：
（1）绝大多数面试官都已经不清楚了KMP算法，他们又不天天刷题。
（2）考KMP没法区分出candidiate的好坏，会做只能说明他最近花时间研究了KMP。 |
|
z**********8
发帖数: 2049 | 27 纽约那个球队，这个周末又要下来挑战我们了。。。紧张而兴奋的期待
听说纽约那个队，前几天聚餐的时候，专门讨论如何对付我们！而且已经在筹划参加明年的acvb比赛的事了。 真是未雨绸缪啊。。。看来我们也要抓紧了。。。
那个纽约“kmp“ 队，自从波士顿对上以后， 就 跟我们纠缠上了。 先把我们的主力队员詹姆士诱骗过去， 接着还招募了好几个 在纽约好几个leagues 混的球油子。实力已经不可同日而语。
第一次较量， 我们主力对阵，几乎”平分秋色“。我们靠了一点点运气， 赢下关键的第三局。第二局被”横扫“。接下来的几局，替补阵容迎战，kmp都轻松赢得比赛。
第二次较量， 纽约kmp，来了5人，包括第一次出战的尼克。我们把伤愈复出的，我们球队第一”塔“-188，借给了他们。 友谊第一，比赛第二嘛！ 不过， 可惜，188没有发挥出应有的水平。可能是刚刚伤愈球有点生，也可能是跟纽约队的二传配合问题。 我们比较轻松的赢得了比赛。当然 纽约kmp的不会服气的。
果然，只不过过了几个星期，他们又电话我，要来”踢馆“。 反正是兵来将挡，水来土掩。谁怕谁！
第三次较量， 纽约可谓是倾巢出动，7个人，所有的主力 |
|
l*****g
发帖数: 685 | 28 KMP是用于找出所有matches in one traveral of the string
譬如，从 abcdabcaabcbc 里找abc, 用 KMP 就可以找出 3 matches
LZ的问题是：找出match, 删除，再在结果里找match, 再删除，直到结果里无match为止
过程如下：
input: abcdabcaabcbc
find matches: [abc]d[abc]a[abc]bc
delete matches: dabc
find matches again: d[abc]
delete matches: d
no more match
output: d
这儿recursively地做了两次find-->delete；如果把KMP用于每一次recursion, 单个
recursion的复杂度是 O(n), 但多个recursion的总的复杂度还是会累加 |
|
g**e
发帖数: 6127 | 29 O(n) time, O(1) space based on KMP. Here I used an utility ArrayList but it
can be removed to do in-place.
public static void recursiveDelete(String target, String pattern) {
if (target == null || pattern == null || pattern.length() ==
0
|| target.length() == 0)
return;
// convert target string into a ArrayList of char
ArrayList charset = new ArrayList();
... 阅读全帖 |
|
s*****y
发帖数: 897 | 30 第2题
可否这样子：
1. 扫描B，建hashtable，同时建KMP的东西
2. 扫描A，如果出现不在Hashtable的字符，就删除这个字符，然后把删除的字符数目
存在上一个在B里面出现的字符里面。
3. KMP搜索压缩后的A，找到所有match的string，计算长度，长度=B的长度+每个match的字符对
应的后面删除的字符数目。update一个全局的最小长度。
例子，adbezcgfiacbdcabc 找a b c
压缩A成为 a1b2c3a0c0b0a0b0c0 每个数字代表后面删除的字符数量.数字单独存在一个
数组里面
然后KMP搜索abcacbabc，第一个abcmatch 得到长度6
最后一个abc match，得到长度3。 |
|
b*****c
发帖数: 1103 | 31 String Similarity
为啥米KMP会超时呢，不是死循环，我测过100000的，只过了4/10 test case
int test_num;
char str[100024];
int F[100024];
long long ans;
void FailureFunction(char P[], int F[],int m){
int i,j;
F[0]=0; // assignment is important!
j=0;
i=1;
while(i
if(P[i]==P[j]){
F[i]=j+1;
i++;
j++;
}else if(j>0){
j=F[j-1];
}else {
F[i]=0;
i++;
}
}
}
void solve(int m)
{
int i=m;
int... 阅读全帖 |
|
p*****2
发帖数: 21240 | 32
我不懂KMP，也没用KMP。看了下wiki上的KMP，试了试，没什么感觉。最后就是用brute
force。 |
|
s*****1
发帖数: 134 | 33 这题我用了三种方法做:
1) Rabin–Karp, 这个方法大小测试时间上均能通过,但是可能是hash function内部实
现的问题,大测试有三个fail了(我在我的电脑上测试了fail的数据,应该是对的)
2) Boyer-Moore, 这个算法好理解,测试也通过了
3) KMP, 这个算法太复杂,没怎么弄明白,写了书上的code,大数据居然exceed time
limit了.
想问大牛们:
1. 你们做这题时,用Rabin-Karp是不是也遇到我这种情况?
2. KMP不是优于BM嘛,为何会超时?
3. 一般KMP面试考吗?如考,怎么考?
谢谢啦 |
|
A*********c
发帖数: 430 | 34 btw, 我觉得lz小看面试官了，他要是问strstr的话必然知道KMP。
这毕竟是他挑的题。你想他一个题面了那么多人，肯定有N个人曾经写过KMP，看都看会
了。
我觉得能把KMP解释清楚的人的个数远远小于能写出来的人个数。
他应该是在求解释。 |
|
w*******u
发帖数: 10 | 35 一月初申请的，一天后就有回复。
好不容易得到的面试机会，没有立刻book店面（本人高能物理PHD，还没毕业，去年下
半年决定找马工工作；自己觉得博士期间科研干得不错，也做很多coding和大数据处理
，可惜只有FLG理我，而且由于初期准备不足，都挂了）。
上周第一次店面，和面试官聊得很好，题目比较简单，水过。 具体如下：
1. leetcode那道soduku solver
2. 写个数据结构，完成各个member function，什么set, get, insert，delete啊
面试完基本上十分钟内就收到回复，说进入第二轮。
第二轮是一个女面试官（他家就那么几个人，只能说这么多了）。google-hangout老连
接出问题（不得不抱怨，更新后的g-talk不给力啊！），折腾了半天，原计划4点开始
的店面拖到4：20。后来无奈之下转投skype，开始：
1. 聊了半天我得背景。前两天刚看别人经验贴，说是要好好利用暖场时间，于是
就聊开了；从后来结果来看，在这个上面花时间有点长了，不如直接上题。
2. 给一个文件，中间有若干A，B string，找... 阅读全帖 |
|
h********3
发帖数: 2075 | 36 大数据情况下，KMP跟直接两两遍历没啥大的区别。实际当中没人用KMP算法，KMP只能
起到五十步笑百步的作用。你应该考虑的是如何从O(n^2)降低到O(n)。 |
|
b***e
发帖数: 1419 | 37 对于每一个V和P，求V和reverse(V)的KMP。然后用KMP(V)从前向后扫一遍P，用KMP(
reverse(V))从后向前扫一遍P，几下所有partial match的起始。组后扫一遍所有
partial matches，看有没有能在一个点对上并且长度合适的。这样整个的算法是线性
的。 |
|
f******h
发帖数: 45 | 38 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
a******d
发帖数: 82 | 39 KMP 解释的很清楚。 基础解法说了，然后说KMP可以用来优化。 不用回跳指针。
没背题，只是知道KMP怎么work的。
不认为表达和交流有明显问题。 |
|
a*****u
发帖数: 1712 | 40 你逻辑是体育老师教的？有个人被面kmp引以为豪，就说明这个出top x题目的面试官是
期望你会kmp？
楼上有小同学被面KMP 还引以为豪， 不是我说的，他的经验证明了确实有出题者出这
种没有意义的题 |
|
S***w
发帖数: 1014 | 41 HR说只有 背景聊天， 还是面了2道算法
一半时间聊behavior questions
然后说做题吧， 真想说， HR说不考题啊
1. strstr
就用最简单那个办法，
我说还有rolling hash Rabin-Karp算法， KMP 但是没让我写
写的话， 我也会Rabin-Karp算法, 但不会KMP
2. 3 sum
两题都不难 , 觉得大家都能答上来，没法出彩
1) 没上KMP |
|
a*******g
发帖数: 1221 | 42 KMP我到现在都没有找到一个好的讲解，wikipedia上的kmp是错的，那个算法是个死循
环。我在谷歌上搜了10多个文章也没有能讲得明白的。KMP最核心的是那个roll back的
算法思想，在roll back时用的是一个循环，但网上的例子都是循环一次就结束了，那
还为啥用循环呢？用if就得了呗？什么例子能利用上那个循环呢？难道是text=aaaaaa,
pattern=aaa这样的例子？ |
|
r*****s
发帖数: 1815 | 43 再送你一句，不过这句要看一点悟性
KMP算法的预处理是维护一个辅助数组，i位置上的值是原数组0-i等于后缀的最大前缀
；KMP算法的匹配是失配后迅速把等于后缀的最大前缀移动到后缀位置继续试图匹配
所以面试手写KMP也没什么大不了的，写不出来的我都给拒了。
: 这题真心是代码简单逻辑不简单
|
|
z**********8
发帖数: 2049 | 44 （2）
这次比赛，起因于波士顿比赛，在同纽约kmp较量中， 实力明显占优的ru队，竟然输掉
了第一局，kmp队中据说有两位的发挥极其出色。wz和tina. 尤其是身高178的女将tina
的发球，硬是把ru的几位主力发晕了。因为时间原因，两队没有完成第二局的比赛。相
约回去后，“补赛”。 不过即使如此， 也已经够“尴尬”的了。没有一传的球队，真
的是谁都能欺负。：（
kmp这次是有备而来，他们再次调整了阵容，recruit了lyf和身高184的jw, 本来还有一
个182左右的强力主攻, nick. 虽然阵中少了一个tina, 给防守一传和发球，带来一点
下降，但是他们网上的攻击力和拦网能力提升了一截。而且，他们在比赛前一天，还在
某队员家里，磨合阵容，商量对策，还企图灌醉ru的某主力队员。
而反观ru, 一个身高接近185的“老油条”主力副攻因故不能参赛，给原来就显“稚嫩
”的队伍，带来了更大的不确定性。好在是主场作战，以逸待劳。我个人的看法，觉得
应该是半斤八两，我们的配合好一点，但是对方的实力更平均，“球”更熟一点。
那个让人熬的周日终于来了。。。 |
|
b**********r
发帖数: 134 | 45 kmp越来越烂了，上个月刚从kmp换到了kmp原作的后续作品potplayer |
|
w*********g
发帖数: 30882 | 46 Da Ji Yuan style.
The author never mentioned that KMP gave up the three northeast provinces
without shooting one bullet. If KMP had not given up, we would not have had
to fight in China North and China South areas. |
|
g*******y
发帖数: 1930 | 47 好像可以把substr再按照*的位置，划分为若干subsubstr,然后用KMP一个一个找出现的位置，假设subsubstr是abc,d?ef,...，用KMP在string中找到第一个abc出现的位置，然后在c出现之后的string里继续再找d?ef的位置。。。用递归也可以做，速度慢些。
对于?的处理，可以这样处理吧,在比较str和subsubstr的时候，自定义个bool
equalChar(char c1,char c2){ return c1==c2 || c2=='?'}来代替普通的c1 == c2判定。
PS,请问一下lz是怎么拿到ms电面的呢，internal refer，career fair，还是裸投简历？ 谢谢。 |
|
b***e
发帖数: 1419 | 48 kmp construstion also needs to take ? as wild-card, otherwise your kmp table
is wrong.
match，可以用DP的方法，类似于今年code jam qualification的最后一题。 |
|
g*******y
发帖数: 1930 | 49 if ? is treated as a normal char when compute KMP table,consider:
str: ababcd....
substr:ab?d
if ? is treated as a Wildcard when compute KMP table, consider:
str: abebcd....
substr:ab?d |
|
