发布时间 : 星期六 文章KMP算法与一个经典概率问题更新完毕开始阅读
方。设f[i,j]表示第i次抛掷硬币后恰好匹配到模式串第j位有多少种情况，则f[i,j]=Σf(i-1,k) + Σf(i-1,l)，其中k满足c[k,0]=j，l满足c[l,1]=j。将f[i,j]除以2的i次方，我们就得到了相应的概率值。或者更直接地，设P[i,j]表示第i次抛掷硬币后，最远能匹配到的模式串位置是第j位的概率，则P[i,j]=Σ( P(i-1,k)/2 ) + Σ( P(i-1,l)/2 )。注意，我们还应该添加一种特殊的概率值P[i,*]，它表示在主串第i个字符以前已经成功匹配过的概率，这样的话下表中每一列的和才能为1。
来看一看程序的输出结果： Pattern 1: s[]=\
主串位置 1 2 3 4 5 6 7 8 9 10
匹配到s[0] 0.5000 0.2500 0.2500 0.2500 0.2188 0.1875 0.1641 0.1445 0.1270 0.1113 匹配到s[1] 0.5000 0.5000 0.3750 0.3125 0.2813 0.2500 0.2188 0.1914 0.1680 0.1475 匹配到s[2] 0.0000 0.2500 0.2500 0.1875 0.1563 0.1406 0.1250 0.1094 0.0957 0.0840 匹配到s[3] 0.0000 0.0000 0.1250 0.1250 0.0938 0.0781 0.0703 0.0625 0.0547 0.0479 已找到匹配 0.0000 0.0000 0.0000 0.1250
0.2500 0.3438 0.4219 0.4922 0.5547 0.6094 Pattern 2: s[]=\
主串位置 1 2 3 4 5 6 7 8 9 10
匹配到s[0] 0.5000 0.2500 0.1250 0.0625 0.0313 0.0156 0.0078 0.0039 0.0020 0.0010 匹配到s[1] 0.5000 0.5000 0.5000 0.4375 0.3750 0.3125 0.2578 0.2109 0.1719 0.1396 匹配到s[2] 0.0000 0.2500 0.2500 0.2500 0.2188 0.1875 0.1563 0.1289 0.1055 0.0859 匹配到s[3] 0.0000 0.0000 0.1250 0.1250 0.1250 0.1094 0.0938 0.0781 0.0645 0.0527 已找到匹配 0.0000 0.0000 0.0000 0.1250 0.2500 0.3750 0.4844 0.5781 0.6563 0.7207 这下我们可以清楚地看到，序列二提前出现的概率要大得多。注意到，根据我们的概率定义，表格中每一列的数字之和都是1。同时，倒数第二行的数字之和（有无穷多项）也应该为1，因为最后一行的概率就是倒数第二行的概率值累加的结果，而根据最后一行概率的定义，主串无穷长时已找到匹配的概率应该为1。因此，我们也可以把倒数第二行看作是模式串在主串第i个位置首次匹配成功的概率。我们可以根据这一结果近似地计算出抛掷次数的期望值。
kmp算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息。 目录
kmp算法-学习介绍
详细算法：一般的KMP算法 KMP算法的优化 基本思想 BM算法
基本思想kmp算法-学习介绍 详细算法： 一般的KMP算法 KMP算法的优化 基本思想 BM算法 基本思想
展开 编辑本段kmp算法-学习介绍
完全掌握KMP算法思想 学过数据结构的人，都对KMP算法印象颇深。尤其是新手，更是难以理解其涵义，搞得一头雾水。今天我们就来面对它，不将它彻底搞懂，誓不罢休。 如今，大伙基本上都用严蔚敏老师的书，那我
就以此来讲解KMP算法。 严老的《数据结构》79-84页讲了基本的匹配方法，这是基础。先把这个搞懂了。 80页在讲KMP算法的开始先举了个例子，让我们对KMP的基本思想有了最初的认识。目的在于指出“由此，在整个匹配的过程中，i指针没有回溯，”。 在此也推荐张铭、赵海燕、王腾蛟编著的《数据结构与算法》一书（北京大学出版社），里面的“字符串”一章对KMP算法有较为详尽易懂的介绍。 编辑本段详细算法： 一般的KMP算法
现在讨论一般情况。 假设 主串：s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 ：p: ‘p(1) p(2) p(3)…..p(m)’ 把课本上的这一段看完后，继续 现在我们假设 主串第i个字符与模式串的第j(j<=m)个字符‘失配’后，主串第i个字符与模式串的第k(k<j)个字符继续比较 此时，s(i)≠p(j), 有 主串： S(1)…… s(i-j+1)…… s(i-1) s(i)
…………. || (相配) || ≠(失配) 匹配串： P(1) ........... p(j-1) p(j) 由此，我们得到关系式 ‘p(1) p(2) p(3)…..p(j-1)’ = ’