能不能讨论一下kmp# JobHunting - 待字闺中
w*0
1 楼
大牛们能否给介绍介绍kmp。看了好几个版本的讲解，都还不是很清楚。到底那个表是
按照什么rule建立起来的。看着逻辑很混乱。有没有大牛能给他简单易懂的版本。或者
给推荐一个比较好的链接。
万分感谢！！！
按照什么rule建立起来的。看着逻辑很混乱。有没有大牛能给他简单易懂的版本。或者
给推荐一个比较好的链接。
万分感谢！！！
m*a
2 楼
看了不少，还是觉得Matrix67的写的是最能看明白的。http://www.matrix67.com/blog/archives/115
TopCoder上那个也不错。
TopCoder上那个也不错。
w*0
3 楼
谢谢。topcoder上的看了，只能明白前面那个RK， 后面的kmp还是有点晕。
我看看这个。谢谢了
【在 m*********a 的大作中提到】
: 看了不少，还是觉得Matrix67的写的是最能看明白的。http://www.matrix67.com/blog/archives/115
: TopCoder上那个也不错。
我看看这个。谢谢了
【在 m*********a 的大作中提到】
: 看了不少，还是觉得Matrix67的写的是最能看明白的。http://www.matrix67.com/blog/archives/115
: TopCoder上那个也不错。
i*t
4 楼
找组数据在纸上走一下就懂
s*l
5 楼
CLRS上有详细介绍
s*x
6 楼
CLRS好多东西讲的晦涩难懂。
【在 s********l 的大作中提到】
: CLRS上有详细介绍
p*2
7 楼
这个东西太复杂了 面试碰到直接跪算了
【在 w********0 的大作中提到】
: 大牛们能否给介绍介绍kmp。看了好几个版本的讲解，都还不是很清楚。到底那个表是
: 按照什么rule建立起来的。看着逻辑很混乱。有没有大牛能给他简单易懂的版本。或者
: 给推荐一个比较好的链接。
: 万分感谢！！！
【在 w********0 的大作中提到】
: 大牛们能否给介绍介绍kmp。看了好几个版本的讲解，都还不是很清楚。到底那个表是
: 按照什么rule建立起来的。看着逻辑很混乱。有没有大牛能给他简单易懂的版本。或者
: 给推荐一个比较好的链接。
: 万分感谢！！！
x*a
8 楼
面试的时候曾经有人问过我kmp，我说了一下大概思想，就是不用回头从i+1开始重新
compare，但是具体不记得了，需要查一下资料brush up一下。
对方也给了我offer，没有任何不悦。但是那是三年前的行情了。
所以我觉得不需要准备这个。
compare，但是具体不记得了，需要查一下资料brush up一下。
对方也给了我offer，没有任何不悦。但是那是三年前的行情了。
所以我觉得不需要准备这个。
z*g
9 楼
大概说一下我的理解吧：
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 table的版本了。这个版本
无法真正做到match = transition(match, str[i])，而是需要通过当前对比结果来做
出判断（比较str[i]和pattern[match]）。如果匹配则match = match + 1，i也可以前
进；如果不匹配，就需要计算match = pmt[match]，而已经用过的str[i]还得拿出来再
用，直至str[i]被匹配或match==0时才可以跳过。注意match = pmt[match]是只减不增
的，因为它的含义是获取在pattern[0, match]中最长的matching proper prefix and
suffix的长度。这个版本的优点是O(n)建表，在pattern重复率不高的情况下几乎可以
一直前进。缺点除了难理解几乎没有。
具体建表方式就不说了，那个配合图看很好理解。
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 table的版本了。这个版本
无法真正做到match = transition(match, str[i])，而是需要通过当前对比结果来做
出判断（比较str[i]和pattern[match]）。如果匹配则match = match + 1，i也可以前
进；如果不匹配，就需要计算match = pmt[match]，而已经用过的str[i]还得拿出来再
用，直至str[i]被匹配或match==0时才可以跳过。注意match = pmt[match]是只减不增
的，因为它的含义是获取在pattern[0, match]中最长的matching proper prefix and
suffix的长度。这个版本的优点是O(n)建表，在pattern重复率不高的情况下几乎可以
一直前进。缺点除了难理解几乎没有。
具体建表方式就不说了，那个配合图看很好理解。
s*l
10 楼
看思想 不要看那些公式
【在 s**x 的大作中提到】
:
: CLRS好多东西讲的晦涩难懂。
【在 s**x 的大作中提到】
:
: CLRS好多东西讲的晦涩难懂。
a*e
11 楼
曾经问过，7月份的时候花了好多时间搞清楚，现在又忘了，就记得个大概。而且以前
看着很清楚的网页现在一看没有啦。。。。。。。觉得还是看图最清楚
http://www.mitbbs.com/article_t/JobHunting/32742535.html
找到一个解释比wiki清楚的source
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.h
下面是根据那个原理写的KMP，这下觉得清楚多了。和正在学习的同学共享一下。。。
。。。顺便多谢各位。。。。
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int pos = kmpSearch(haystack, needle);
if (pos == -1) return nullptr;
else return haystack + pos;
}
static void kmpPreprocess(const char *p, vector &b)
{
int i = 0, j = -1;
b[i] = j;
const int m = strlen(p);
while (i
while (j >= 0 && p[i] != p[j]) j = b[j];
i++; j++;
b[i] = j;
}
}
static int kmpSearch(const char *t, const char *p)
{
int i = 0, j = 0;
int n = strlen(t);
int m = strlen(p);
if (m==0) return 0;
// int *b = new int[m+1];
vector b(m+1,0);
kmpPreprocess(p, b);
while (i
while (j >= 0 && t[i] != p[j]) j = b[j];
i++; j++;
if (j == m)
{
//delete[]b;
return (i - j);
}
}
return -1;
}
};
看着很清楚的网页现在一看没有啦。。。。。。。觉得还是看图最清楚
http://www.mitbbs.com/article_t/JobHunting/32742535.html
找到一个解释比wiki清楚的source
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.h
下面是根据那个原理写的KMP，这下觉得清楚多了。和正在学习的同学共享一下。。。
。。。顺便多谢各位。。。。
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int pos = kmpSearch(haystack, needle);
if (pos == -1) return nullptr;
else return haystack + pos;
}
static void kmpPreprocess(const char *p, vector
{
int i = 0, j = -1;
b[i] = j;
const int m = strlen(p);
while (i
while (j >= 0 && p[i] != p[j]) j = b[j];
i++; j++;
b[i] = j;
}
}
static int kmpSearch(const char *t, const char *p)
{
int i = 0, j = 0;
int n = strlen(t);
int m = strlen(p);
if (m==0) return 0;
// int *b = new int[m+1];
vector
kmpPreprocess(p, b);
while (i
while (j >= 0 && t[i] != p[j]) j = b[j];
i++; j++;
if (j == m)
{
//delete[]b;
return (i - j);
}
}
return -1;
}
};
b*g
12 楼
也看过不少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
if(needle[i]==needle[j+1]) j++;
match[i] = j;
}
return match;
}
int strStr(char *haystack, char *needle) {
if(!*needle) return 0;
if(!*haystack) return -1;
int n = strlen(haystack);
int m = strlen(needle);
vector match = KMPpreprocessing(needle);
int j = -1;
for(int i=0; i
if(haystack[i]==needle[j+1]) j++;
if(j==m-1) return i-m+1;
}
return -1;
}
感觉KMP的精髓就在于这一步：
while(j>=0 && needle[i]!=needle[j+1]) j = match[j];
理解了这步递推其他就容易理解了。
的strStr()这题是用土办法2 points做的，今天也跟风写了个KMP版的strStr()过了下
lc.
BTW: 今天才发现lc这题的interface改了，以前是返回指针，现在变成返回起始index
了。
vector
int m = strlen(needle);
// assume j = match[i]: needle[i-j:i] == needle[0:j]
vector
int j = -1;
for(int i=1; i
if(needle[i]==needle[j+1]) j++;
match[i] = j;
}
return match;
}
int strStr(char *haystack, char *needle) {
if(!*needle) return 0;
if(!*haystack) return -1;
int n = strlen(haystack);
int m = strlen(needle);
vector
int j = -1;
for(int i=0; i
if(haystack[i]==needle[j+1]) j++;
if(j==m-1) return i-m+1;
}
return -1;
}
感觉KMP的精髓就在于这一步：
while(j>=0 && needle[i]!=needle[j+1]) j = match[j];
理解了这步递推其他就容易理解了。
h*s
13 楼
你写的这个比matrix67的pseudo code更清楚。
while(j>=0 && needle[i]!=needle[j+1]) j = match[j];
其中的 needle[j+1] 和初始化的 -1 结合起来巧妙的处理了起始情况的判断。
谢谢好code，赞!!!
lc
index
【在 b******g 的大作中提到】
: 也看过不少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;
while(j>=0 && needle[i]!=needle[j+1]) j = match[j];
其中的 needle[j+1] 和初始化的 -1 结合起来巧妙的处理了起始情况的判断。
谢谢好code，赞!!!
lc
index
【在 b******g 的大作中提到】
: 也看过不少KMP的讲解，觉得确实是matrix67讲得最清楚。CLRS讲得太生涩。之前刷lc
: 的strStr()这题是用土办法2 points做的，今天也跟风写了个KMP版的strStr()过了下
: lc.
: BTW: 今天才发现lc这题的interface改了，以前是返回指针，现在变成返回起始index
: 了。
: vector
: int m = strlen(needle);
: // assume j = match[i]: needle[i-j:i] == needle[0:j]
: vector
: int j = -1;
a*r
14 楼
这个递推的精髓就是要能看懂 CLRS那个引理的证明, 即集合PI*(i) 是P_i所有的
suffix的集合。花半个小时, 好好看看书上证明。各种符号都在那个章节第一页定义了。
lc
index
【在 b******g 的大作中提到】
: 也看过不少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;
suffix的集合。花半个小时, 好好看看书上证明。各种符号都在那个章节第一页定义了。
lc
index
【在 b******g 的大作中提到】
: 也看过不少KMP的讲解，觉得确实是matrix67讲得最清楚。CLRS讲得太生涩。之前刷lc
: 的strStr()这题是用土办法2 points做的，今天也跟风写了个KMP版的strStr()过了下
: lc.
: BTW: 今天才发现lc这题的interface改了，以前是返回指针，现在变成返回起始index
: 了。
: vector
: int m = strlen(needle);
: // assume j = match[i]: needle[i-j:i] == needle[0:j]
: vector
: int j = -1;
b*g
15 楼
是的，的确就是那个证明。当时看CLRS花了不少时间是硬看懂了。后来发现如果要上手
理解这个算法还是matrix67讲得浅出一些。觉得先看一遍matrix67讲得搞明白算法到底
是干啥的，怎么运作的，然后回头看CLRS的严格证明，会更省时间点，更轻松愉快点。
CLRS因为是一本很严谨的教科书，往往阐述时容易用很精确但是冗长的定义来讲，我个
人的感受一些比较复杂的算法有时候第一遍看的时候会lost在一些长句定义中。而如果
已经大概知道这算法是怎么样的再看，会感叹原来可以把算法的正确性和复杂度证明得
如此到位。
了。
【在 a********r 的大作中提到】
: 这个递推的精髓就是要能看懂 CLRS那个引理的证明, 即集合PI*(i) 是P_i所有的
: suffix的集合。花半个小时, 好好看看书上证明。各种符号都在那个章节第一页定义了。
:
: lc
: index
理解这个算法还是matrix67讲得浅出一些。觉得先看一遍matrix67讲得搞明白算法到底
是干啥的，怎么运作的，然后回头看CLRS的严格证明，会更省时间点，更轻松愉快点。
CLRS因为是一本很严谨的教科书，往往阐述时容易用很精确但是冗长的定义来讲，我个
人的感受一些比较复杂的算法有时候第一遍看的时候会lost在一些长句定义中。而如果
已经大概知道这算法是怎么样的再看，会感叹原来可以把算法的正确性和复杂度证明得
如此到位。
了。
【在 a********r 的大作中提到】
: 这个递推的精髓就是要能看懂 CLRS那个引理的证明, 即集合PI*(i) 是P_i所有的
: suffix的集合。花半个小时, 好好看看书上证明。各种符号都在那个章节第一页定义了。
:
: lc
: index
相关阅读
请问一下S家的职称序列请问板上有人能够内推slack的吗houzz 怎么没人提了？看到很合适的硬件工程师职位，求内推facebookFacebook, Two Sigma Offer求比较无人驾驶---导航方向--数据挖掘 ==base深圳Startup内推 new grad也可求new grad的内推吾波第三季亏损再破记录"Save" jobs by starting a trade war !!!我厂钞票印刷团队某经理求亚马逊group面（群面）的有意义的面筋4月公司帮申到h1b，但在10月生效前辞职有事回国h1b gap中间找到工作，是要file新h1b transfer之前离境么？有大数据方面的专家想回国工作的吗？Airbnb值30B微软内部transfer 求收留各公司员工待遇对比一句话告诉你“外F 和 外嫁的区别” (转载)你G竟然没拒，喜剧也很悲剧，怎么办？