2006-11-29 20:02| 
153 Comments | 本文内容遵从 如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。
我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I'm matrix67"，字符串B="matrix"，我们就说B是A的子串。你可以委婉地问你的MM：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？”
解决这类问题，通常我们的方法是枚举从A串的什么位置起开始与B匹配，然后验证是否匹配。假如A串长度为n，B串长度为m，那么这种方法的复杂度是O (mn)的。虽然很多时候复杂度达不到mn（验证时只看头一两个字母就发现不匹配了），但我们有许多“最坏情况”，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我们将介绍的是一种最坏情况下O(n)的算法（这里假设 m<=n），即传说中的KMP算法。
之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。这时，或许你突然明白了AVL 树为什么叫AVL，或者Bellman-Ford为什么中间是一杠不是一个点。有时一个东西有七八个人研究过，那怎么命名呢？通常这个东西干脆就不用人名字命名了，免得发生争议，比如“3x+1问题”。扯远了。
个人认为KMP是最没有必要讲的东西，因为这个东西网上能找到很多资料。但网上的讲法基本上都涉及到“移动(shift)”、“Next函数”等概念，这非常容易产生误解（至少一年半前我看这些资料学习KMP时就没搞清楚）。在这里，我换一种方法来解释KMP算法。
假如，A="abababaababacb"，B="ababacb"，我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时，i和j各加一；什么时候j=m了，我们就说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。当A[i+1]<>B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。我们看一看当 i=j=5时的情况。
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
此时，A[6]<>B[6]。这表明，此时j不能等于5了，我们要把j改成比它小的值j'。j'可能是多少呢？仔细想一下，我们发现，j'必须要使得B[1..j]中的头j'个字母和末j'个字母完全相等（这样j变成了j'后才能继续保持i和j的性质）。这个j'当然要越大越好。在这里，B [1..5]="ababa"，头3个字母和末3个字母都是"aba"。而当新的j为3时，A[6]恰好和B[4]相等。于是，i变成了6，而j则变成了 4：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
从上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组P[j]，表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。
再后来，A[7]=B[5]，i和j又各增加1。这时，又出现了A[i+1]<>B[j+1]的情况：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
由于P[5]=3，因此新的j=3：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
这时，新的j=3仍然不能满足A[i+1]=B[j+1]，此时我们再次减小j值，将j再次更新为P[3]：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
现在，i还是7，j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样，j必须减小到P[1]，即0：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7
终于，A[8]=B[1]，i变为8，j为1。事实上，有可能j到了0仍然不能满足A[i+1]=B[j+1]（比如A[8]="d"时）。因此，准确的说法是，当j=0了时，我们增加i值但忽略j直到出现A[i]=B[1]为止。
这个过程的代码很短（真的很短），我们在这里给出：
j:=0;
for i:=1 to n do
begin
while (j>0) and (B[j+1]<>A[i]) do j:=P[j];
if B[j+1]=A[i] then j:=j+1;
if j=m then
begin
writeln('Pattern occurs with shift ',i-m);
j:=P[j];
end;
end;
最后的j:=P[j]是为了让程序继续做下去，因为我们有可能找到多处匹配。
这个程序或许比想像中的要简单，因为对于i值的不断增加，代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串A，并更新可以匹配到B的什么位置。
现在，我们还遗留了两个重要的问题：一，为什么这个程序是线性的；二，如何快速预处理P数组。
为什么这个程序是O(n)的？其实，主要的争议在于，while循环使得执行次数出现了不确定因素。我们将用到时间复杂度的摊还分析中的主要策略，简单地说就是通过观察某一个变量或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小（但不能减成负的），而另外的改变j值的地方只有第五行。每次执行了这一行，j都只能加1；因此，整个过程中j最多加了n个1。于是，j最多只有n次减小的机会（j值减小的次数当然不能超过n，因为j永远是非负整数）。这告诉我们，while循环总共最多执行了n次。按照摊还分析的说法，平摊到每次for循环中后，一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这样的分析对于后面P数组预处理的过程同样有效，同样可以得到预处理过程的复杂度为O(m)。
预处理不需要按照P的定义写成O(m^2)甚至O(m^3)的。我们可以通过P[1],P[2],...,P[j-1]的值来获得P[j]的值。对于刚才的B="ababacb"，假如我们已经求出了P[1],P[2],P[3]和P[4]，看看我们应该怎么求出P[5]和P[6]。P[4]=2，那么P [5]显然等于P[4]+1，因为由P[4]可以知道，B[1,2]已经和B[3,4]相等了，现在又有B[3]=B[5]，所以P[5]可以由P[4] 后面加一个字符得到。P[6]也等于P[5]+1吗？显然不是，因为B[ P[5]+1 ]<>B[6]。那么，我们要考虑“退一步”了。我们考虑P[6]是否有可能由P[5]的情况所包含的子串得到，即是否P[6]=P[ P[5] ]+1。这里想不通的话可以仔细看一下：
1 2 3 4 5 6 7
B = a b a b a c b
P = 0 0 1 2 3 ?
P[5]=3是因为B[1..3]和B[3..5]都是"aba"；而P[3]=1则告诉我们，B[1]、B[3]和B[5]都是"a"。既然P[6]不能由P[5]得到，或许可以由P[3]得到（如果B[2]恰好和B[6]相等的话，P[6]就等于P[3]+1了）。显然，P[6]也不能通过P[3]得到，因为B[2]<>B[6]。事实上，这样一直推到P[1]也不行，最后，我们得到，P[6]=0。
怎么这个预处理过程跟前面的KMP主程序这么像呢？其实，KMP的预处理本身就是一个B串“自我匹配”的过程。它的代码和上面的代码神似：
P[1]:=0;
j:=0;
for i:=2 to m do
begin
while (j>0) and (B[j+1]<>B[i]) do j:=P[j];
if B[j+1]=B[i] then j:=j+1;
P[i]:=j;
end;
最后补充一点：由于KMP算法只预处理B串，因此这种算法很适合这样的问题：给定一个B串和一群不同的A串，问B是哪些A串的子串。
串匹配是一个很有研究价值的问题。事实上，我们还有后缀树，自动机等很多方法，这些算法都巧妙地运用了预处理，从而可以在线性的时间里解决字符串的匹配。我们以后来说。
昨天发现一个特别晕的事，知道怎么去掉BitComet的广告吗？把界面语言设成英文就行了。
还有，金山词霸和Dr.eye都可以去自杀了，Babylon素王道。
Matrix67原创
转贴请注明出处
153 条回复
您也随便说几句吧：
MM说：我的告白语是“其实。。。我喜欢的并不是matrix67，我喜欢的是你啊，Hotdog”
恭喜你。。你是她告白语里的子串。
回复：你的英文名字咋不是sour-and-hot dog ?
你说的比数据结构还要好
不过kmp是我到目前为止唯一没有实现的东西。一律用prefix tree......所以不会写kmp
回复：前缀树？
您的预处理程序代码有问题...
回复：谢谢提醒，已改正；我错把B写成P了
请问代码关键字高亮您是怎么弄的？
回复：http://www.matrix67.com/blog/article.asp?id=203
sounds interesing.
不过只要一句话个旧可以归纳出来。
find the the model of the shor pattern by self match for shift.
这个算法在notepad上有很多应用。但是，一般用另一个算法：BM
回复：同意
MS懂了，谢谢，但 P[3]=1则告诉我们，B[1]和B[5]都是"a"？B［1］和B［3］吧。
回复：没写错，B[1]=B[3]=B[5]，省略了中间步骤。这里B[1]=B[5]才是我们需要的结论。
good
倒数第七段
这里不大明白，整个过程中j是在回退然后前进的，假设第一遍比较回退一次，第二遍比较回退两次，于是总共加起来j减小和变大的次数都要大于n，不是吗？
回复：我每年新交1个MM，我100年内会失恋200次吗？
其实它是传说中的看毛片算法 我在百度上搜了三篇全是你的 版权问题哟
回复：看毛片算法……嗯，有才
11楼的同学。。。你太。。。了。。。
11楼的同学，这条评论应该加上：
“The comment is R-rated”.
请问为什么我用这个方法去写vijos p1005(超长数字串)会超时,那个题是不是还有更快的方法啊,能不能讲解一下
谢谢
回复：那道题数字串太长，根本不是让你去模拟的，而是直接对输入数据尝试进行“分割”
强烈支持!!!写的简洁透彻,,,
同时鄙视各种吃人饭不干人事教育部的全体博士,教授,导师,博士后等等系列烂人!!!
想请教下所谓"扩展KMP"是什么东西?
请不要回答--由KMP扩展而来....听得太多了.....
搞不懂p[5]=3是怎么一回事，帮忙解释一下
而P[3]=1则告诉我们，B[1]和B[5]都是"a"。
这句话是错的吧？应该是B[1]和B[3]都是“a”吧
回复：b[1]=b[3]=b[5]，我省略了。不少人都有这个疑问，我补充了一下原文。
原来这篇文章是你们的呀！哈哈，找到原文了！
经典，谢谢~~~~~~~~~看到转载的，不过很有礼貌的说了原文出处，就直接过来看了
三周年考古～
能不能给一个具体的例子？
我是初学者，谢谢
嘿嘿
和MM约会........
很好很强大....
留下脚印，见证我曾经被KMP搞昏过..
我终于找到一个能看得懂的了
太谢谢了
太感谢了，真是我们这些菜鸟的福音啊!
强大的Matrix67
终于懂了什么是 看毛片算法了
vijos P1425可以用KMP做吗？我怎么TLE了5个点呢？请教Matrix67牛~
KMP好东西的
大牛兄
[...] http://www.matrix67.com/blog/archives/115】 « [...]
再看看
今晚老师讲课的内容，读完本文后如醍醐灌顶。
不可否认我的低智商，看了好多遍才看懂呵呵谢谢大牛啊
有没有别的比较好的参加NOIP可以用到的算法，如果可以的话请发到我
的邮箱742766614@qq.com
我跟33楼一样
我的邮箱是cyclone77@126.com
主页：http://cyclone77.cn
正是我所要找的,哈哈,谢谢了
发现一个小问题。。。
while (j>0) and (B[j+1]B[i]) do j:=P[j];
这句貌似应该加上一个越界限制判断吧？
while (j>0) and (j+1 < m) and (B[j+1]B[i]) do j:=P[j];
我错了=.= 没理解透，重新看。。。
[...] 继续复习算法+数据结构。今天简单写写KMP算法，不是那个KMPLAYER。。。同时这个话题也有很优秀的博文介绍，如Matrix67，我这里只是做些简单的小结。 [...]
非常感谢你。
good!那么直接的东西 为什么那些课本要那么绕 thx~
好棒！今天，终于懂了KMP算法！
老师上课讲的很模糊 还以为很难 但是看看你的文章一下子就明晰了 多谢~
我的QQ 64076241 希望能和你多交流^_^
为什么我的42楼 与众不同呀
如果直接用copy函数，和kmp比，谁的效率更高啊？
我很菜，5bs
膜拜呀
有个例子讲解太好类
那些没例子的教程都去死吧
写的真好，我终于看懂了，谢谢。
可以写书了 ，绝对经典教材
偶然路过此地，深感惭愧。你真很有才，这个世界牛人多得数不清了：）
有空的时候可不可以在写一篇关于DLX算法的？很期待哟！
[...] 真的不难, 去看看Matrix67的博客就全懂了, 不过我是啃[算法导论]啃懂的, [...]
WASAI 敬仰
^_^写个CPP的好不好？谢谢！
11楼的同学你有些太那个了
I服了U
坚持啃CLRS的人路过……
好吧，膜拜中。。。比dejiwei讲的清楚多了~不过话说是他叫我来看的。
Ps.文章我转了。
传说中KMP讲解的神一般的文章……
很精辟，一个钟头让我明白KMP的实现。。。
没看明白wiki上KMP algorithm的童鞋到此一游。
writeln('Pattern occurs with shift ',i-m);
我觉得应该是i-m+1
这东西写的太tm好了！！！
AC了！
第二自然段中
复杂度应该是 是O ((m-n)n)吧....
嘿嘿...
第六段中出现了一个j=m。m是什么？
Matrix67神牛的文章果然令人受益匪浅，配合《散发导论》效果很好，谢谢。
[...] Matrix67】Kmp算法 八 25 杂 转自Matrix67.blog(kmp算法详解） [...]
这代码是什么语言，是什么符号？
B="ababacb"，...P[4]=2
我想知道这个P[4] = 2 是怎么得出来的.
搜狗打 kmp。。。。。。。。
看了Matrix67大牛的文章感觉就是不一样~
while (j>0) and (B[j+1]A[i]) do j:=P[j];
为什么不是A[i+1]呢？
在文章中不是B[j+1]同A[i+1]比较吗？
不好意思，再次打扰了啊。。。
数组P需要自己求吗？那这样的话，求P数组应该也需要一定时间的吧，那么KMP整个算法的效率应该包含两部分了?
1:求P数组各个值
2:求子串
[...] AC自动机是用于多串匹配的一种数据结构，和KMP一样将时间复杂度降到了线性时间，非常强大实用。 [...]
KMP算法的一个C语言实现...
KMP算法 -> 传送门 M67的原文里是用Pascal实现的,这里发一个移植到C中的代码. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include <stdlib.h> #include <stdio.h> #include <string.h...
[...] 转自：http://www.matrix67.com/blog/archives/115 [...]
谢谢大神指点，一看就懂了
既然P[6]不能由P[5]得到，或许可以由P[3]得到。
为什么不是先检测P[6]是不是由P[4]得到，而越过p[4]检测p[3] ?
j:=P[j]; 而不是j:=j-1 ?
既然P[6]不能由P[5]得到，或许可以由P[3]得到。
为什么不是先检测P[6]是不是由P[4]得到，而越过p[4]检测p[3] ?
j:=P[j]; 而不是j:=j-1 ???
突然发现，和算导上的代码神似
Orz终于将KMP弄懂了、、
I wonder 拓展KMP是神马
看毛片算法...终于懂了
while (j>0) and (B[j+1]A[i]) do j:=P[j];
hi~ 我怎么觉得这句可以用if,不需要while,就是当B[j+1]!=A[i]时就换j,并且你的while也没循环啊,根据摊还复杂度不是O(1)?
why？j'必须要使得B[1..j]中的头j'个字母和末j'个字母完全相等（这样j变成了j'后才能继续保持i和j的性质）。
哇哇~看毛片算法
[...] 看到上面的代码，两层循环，貌似这个代码并不是线性的，其实不然。外层循环了n次这个没有问题，关键是里面的while循环，这个循环的次数是多少并不好确定，然而考虑单单考虑j的值的变化，会发现第七行j增加1，而第6行j则减少，可能减少1，可能减少2，可能少的更多，但是j<0时循环就终止了，也就是说j有n次增加的机会，会有多少次减少的机会？或者问j最多减少多少次？j减少的次数最多的时候，就是每次减少1，这样最多的会减少n次，也就是说第六行的循环最多会执行n次。平摊到每个循环，则执行次数为O(1)，所以kmpSearch的时间复杂度仍然是线性的O(n)，同理，kmpGetNext的时间复杂度为O(m).详情请参考matrix67大牛的文章,下面有犀利的评论： [...]
[...] 这里的B[i]得到的则是S串中以i开头的能匹配模式串的长度，综合一下，就是说KMP得到的是S[i-B[i]+1]..S[i]=T[0]..T[B[i]-1]，而扩展KMP则是说S[i]..S[i+B[i]-1]=T[0]..T[B[i]-1]，这样差别就比较明显了，然后就是每次求后面的都是利用了之前求出的内容来推出后面的，具体还是不明白的话可以查看matrix67大牛的KMP讲解和我以前写的扩展KMP的内容，还有就是KMP只是单模式串匹配如果多模式串匹配那就是Aho_Corasick自动机了，其实思想还是KMP的思想，一开始的那张图就是Aho_Corasick自动机构造好图的样式了。 然后就是说一下最小表示法又称作最小环排列，是说把一个字符串看成一个环，有n种线性表示（就是说把环切开） ，这里面最小的就是最小环排列，代码 [...]
哈哈谢谢
除了 “P[3] = 1 告诉我们 B[1],B[3],B[5]都是a ”这句话不理解外， 其他真的讲的很容易懂。。。虽然上面的回复中讲过， 但还是有点迷惑。
强大！
NB,强大！
[...] http://www.matrix67.com/blog/archives/115 [...]
[...] 这里的B[i]得到的则是S串中以i开头的能匹配模式串的长度，综合一下，就是说KMP得到的是S[i-B[i]+1]..S[i]=T[0]..T[B[i]-1]，而扩展KMP则是说S[i]..S[i+B[i]-1]=T[0]..T[B[i]-1]，这样差别就比较明显了，然后就是每次求后面的都是利用了之前求出的内容来推出后面的，具体还是不明白的话可以查看matrix67大牛的KMP讲解和我以前写的扩展KMP的内容，还有就是KMP只是单模式串匹配如果多模式串匹配那就是Aho_Corasick自动机了，其实思想还是KMP的思想，一开始的那张图就是Aho_Corasick自动机构造好图的样式了。 然后就是说一下最小表示法又称作最小环排列，是说把一个字符串看成一个环，有n种线性表示（就是说把环切开） ，这里面最小的就是最小环排列，代码 [...]
[...] 然后考虑到这题是字符串处理，用上了KMP（附Matrix67的教程），冲到第三个点。 [...]
[...] http://www.matrix67.com/blog/archives/115 [...]
[...] [1]http://www.matrix67.com/blog/archives/115/ var infolink_pid = 138755; var infolink_wsid = 4; [...]
貌似有问题吧
以下代码
Program KMP;
Const
a='abababaabab';
b='ababa';
Var
i,j:integer;
P:Array[1..10]of integer;
Begin
{Calc P}
P[1]:=0;
j:=0;
for i:=2 to length(b) do
begin
while (j>0) and(B[j+1]B[i]) do j:=P[j];
if B[j+1]=B[i] then inc(j);
P[i]:=j;
End;
j:=0;
for i:=2 to length(a) do
begin
while (j>0)and(B[j+1]a[i]) do j:=P[j];
if B[j+1] = A[i] then inc(j);
if j= length(b) then
begin
writeln(i-length(b));
j:=P[j];
End;
End;
End.
输出的是2哦
竟然是vb 。。。
"110001" in "11010001"?
代码与《算导》上的神似。。。。。。
[...] 文章转载自Matrix67 如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。 [...]
写的太好了，真的获益匪浅。大牛能不能写个BM算法，让我们学习学习。
Orz
Orz
赞详细，看懂了为什么要左边字符串等于右边字符串了！
我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。
M67大牛··弱弱的问一句这句话什么意思？
[...] http://www.matrix67.com/blog/archives/115/ 这篇文章写的很不错； [...]
[...] 出自matrix67.com [...]
[...] From：http://www.matrix67.com/blog/archives/115/ Filed in ACM, Knowledge with 0 Comments 1 views « ubuntu下的一些常用文件（更新ing） [...]
[...] KMP算法详解 [...]
光看这个值就知道博主错了 P = 0 0 1 2 3 ?
回104楼，你看的这个P是没有加优化的，不要觉得人家是错的。
[...] 题意：给你一个字符串，问它最多是由多少个同样的子串构成的。 分析:kmp啊，这是偶的第一个kmp算法题。。这个next数组用法很是巧妙。。。 len-next[len]就是循环节的长度，自己模拟一下就会明白的。。 kmp一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此称之为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作，其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯指针，而是利用已经得到的“部分匹配”结果将模式向左“滑动”尽可能近的一段距离，继续进行比较。 next数组： 模式串P开头的任意个字符，把它称为前缀子串，如p0p1p2…pm-1。在P的第i位置的左边，取出k个字符，称为i位置的左子串，即pi-k+1… pi-2 pi-1 pi。求出最长的（最大的k）使得前缀子串与左子串相匹配称为，在第i位的最长前缀串。第i位的最长前缀串的长度k就是模板串P在位置i上的特征数n[i]特征数组成的向量称为该模式串的特征向量。 如果还是不太明白可看看matrix大牛的博客点击这里 [...]
[...] 关于KMP算法，Matrix67的这篇文章不能错过KMP算法详解。 [...]
你是怎么想到的？
可能我比较笨吧，对于那个p[]是怎么都不懂为什么，他的值是怎么得到的，为什么那样写，while (j>0) and (B[j+1]A[i]) do j:=P[j];这句是为什么
[...] 记一个KMP算法的应用，经典的KMP算法详解还是看这里 [...]
[...] 常用的字符串匹配算法有KMP算法和BM算法，关于KMP算法，可以看这篇文章，相信大家看了这篇文章都可以明白KMP算法的机制。 [...]
[...] KMP详解 [...]
“KMP的预处理本身就是一个B串“自我匹配”的过程”
看了这句话，豁然开朗！
大神？您年方几何了啊，我想跟你交个朋友啊
传说中的看毛片算法
[...] 至于不知道KMP为何物的童鞋可以参考Matrix67大牛的教程：点我。 Categories: SolutionTags: [...]
膜拜。多谢大婶！！会了。o(∩_∩)o 哈哈
[...] 好长时间没在那安安静静的敲代码了，这个星期一直在忙乎各种扯淡的课程设计，论文。周末总算是安静的学了点东西。KMP是处理字符串的高效算法。无论是从时间复杂度还是空间复杂度上来说，KMP都能完胜。他们几个在就学了KMP算法，我这后知后觉的今天总算是学了下KMP。只是简单入门级别的，就这样还是老丁给讲了一下，看了一下matrix67大神的博客，然后自己在那顿悟了一上午。 [...]
[...] 在信息競賽中，我們學到的所謂「KMP（Knuth-Morris-Pratt）算法」通常是這樣的： http://www.matrix67.com/blog/archives/115/ [...]
学习了，谢谢Lz
讲的太清楚了
大大的顶
要顺便介绍扩展kmp，就更好了
[...] kmp的详细算法解析参见Matrix67的博文kmp详解 [...]
[...] 关于字符串匹配，KMP算法也算是经典算法了，因为也是刚学的，所以对算法基本思想就木有什么可说的了，此篇仅作备忘。算法讲解移步http://www.matrix67.com/blog/archives/115 [...]
[...] 想看更详细的KMP讲解，可以看《算法导论》或到Matrix67那里去看看。 [...]
[...] [1] http://www.matrix67.com/blog/archives/115 [...]
[...] [1] http://www.matrix67.com/blog/archives/115 [...]
哈哈哈
[...] [1] http://www.matrix67.com/blog/archives/115 [...]
[...] [1] http://www.matrix67.com/blog/archives/115 [...]
[...] KMP是线性匹配算法。他根据目标串的特性来快速跳过无效匹配位置。具体看这个博客：http://www.matrix67.com/blog/archives/115 这个博客讲的非常清楚，图例非常多。 [...]
太牛了！讲的很浅显易懂！
小岛，是你么？鼓掌啊
这篇文章写的很赞，不过有个疑问，在模式匹配和计算next时候， if B[j+1]=B[i] then j:=j+1;可以简写成 j:=j+1;不需要B[j+1]=B[i]这个判断了，因为上面的while循环之后，要么一定是找到了确实相等，要么到达位置0处，这些状态下都等着相加操作。
[...] http://www.matrix67.com/blog/archives/115/ Author:snow | Categories:代码及源码交流、全部文章 | Tags: ACM、bf、bm、J2MEN、kmp、KMP算法、小应用协会、算法 [...]
[...] Blog – 《KMP算法详解》 + [...]
把这一句while (j>0) and (B[j+1]B[i]) do j:=P[j];直接改成if (j>0) and (B[j+1]B[i]) do j:=0;如何？
把这一句while (j>0) and (B[j+1]B[i]) do j:=P[j];直接改成if (j>0) and (B[j+1]B[i]) then j:=0;如何？
您写得真好，把我的理解硬伤全都瞬秒了~~~
[...] 在学习KMP算法的过程中，我在网络上查了大量的资料。遗憾的是，查到的资料虽多，能讲明白的几乎没有。后来有幸看到了Matrix67写的一篇博文：http://www.matrix67.com/blog/archives/115/，认真揣摩后才茅塞顿开。 [...]
~ ~ ~
感谢Matrix大神的精彩讲解，终于在您这里明白了KMP算法。
使我明白KMP的文章
[...] 下面这些内容引自 http://www.matrix67.com/blog/archives/115 [...]
你的思路比较奇特，个人还是觉得前缀函数的方式比较好理解。毕竟算法的本质就是对pattern的分析后优化的算法
[...] – 《KMP算法详解》 + [...]
[...] 原文链接：http://www.matrix67.com/blog/archives/115 [...]
自己写字符创匹配的时候就觉得BM有些操作是浪费掉的，这很不科学，原来这就是KMP啊。偷懒光荣！浪费可耻！
不要浪费每一步操作和尽量一次都做点儿事是算法优化的关键。KMP是前者
神一样的M67，讲的确实特别清楚
膜拜啊，终于看懂了 ，算导上面没看明白。。。