数据结构- 串的模式匹配算法：BF和 KMP算法

Brute-Force算法的思想

1．BF(Brute-Force)算法

Brute-Force算法的基本思想是：

1) 从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s 的第二个字符起再重新和串t进行比较。

2) 依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。

Brute-Force算法的实现

c语言实现：

2．KMP算法<strong>2.1 算法思想：</strong><p></p><p>每当一趟匹配过程中出现字符比较不等时，不需要回溯I指针，而是利用已经的带的“部分匹配”的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。</p><p>即尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式串的滑动速度。</p><p><img style="max-width: 100%;height: auto;width: auto\9;" src="//img.reader8.net/uploadfile/jiaocheng/20140188/3029/201401301429278093.jpg" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法"><br></p><p><br></p><p><br></p><p><br></p><p>需要讨论两个问题：<br>①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？<br>② 模式应该向右滑多远才是高效率的?<br></p><p></p><p><strong>现在讨论一般情况:</strong></p><p>假设 主串：s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 ：p: ‘p(1) p(2) p(3)…..p(m)’</p><p></p><p>现在我们假设 主串第i个字符与模式串的第j(j&lt;=m)个字符‘失配’后，主串第i个字符与模式串的第k(k&lt;j)个字符继续比较。</p><p>此时，s(i)≠p(j)：<br></p><p><img style="max-width: 100%;height: auto;width: auto\9;" src="//img.reader8.net/uploadfile/jiaocheng/20140188/3029/201401301429278094.jpg" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法"><br></p><p></p><p>由此，我们得到关系式：即得到到1 到<strong> j -1 </strong>的<strong>"部分匹配"</strong>结果:</p><p><strong> ‘P(1) P(2) P(3)…..P(j-1)’ = ’ S(i-j&#43;1)……S(i-1)’</strong></p><p> 从而推导出k 到 j- 1位的“部分匹配”：即P<strong>的<strong>j-1</strong><strong>～</strong><strong>j-k</strong>＝S前i-1～i- (k -1))位 </strong><strong> </strong><strong> </strong></p><p><strong> <strong>‘P(j - k &#43; 1) …..P(j-1)’ = <strong> ’S(i-k&#43;1)S(i-k&#43;2)……S(i-1)’</strong></strong><br></strong></p><p>由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在 k’&gt;k 满足下列关系式：(k&lt;j)<br></p><p><img style="max-width: 100%;height: auto;width: auto\9;" src="//img.reader8.net/uploadfile/jiaocheng/20140188/3029/201401301429278095.jpg" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法" style="font-size:14px"><br></p><p>有关系式： 即(P的前k- 1 ~ 1位＝ S前i-1～i-(k-1) )位 ) ,：</p><p><strong>‘P(1) P(2) P(3)…..P(k-1)’ = ’S(i-k&#43;1)S(i-k&#43;2)……S(i-1)’</strong></p><p></p><p>现在我们把前面总结的关系综合一下,有：</p><p><img style="max-width: 100%;height: auto;width: auto\9;" src="//img.reader8.net/uploadfile/jiaocheng/20140188/3029/201401301429278096.jpg" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法"><br></p><p></p><p>由上，我们得到关系：<br></p><p><strong>‘p(1) p(2) p(3)…..p(k-1)’ = ‘p(j - k &#43; 1) …..p(j-1)’ </strong><br></p> 反之，若模式串中满足该等式的两个子串，则当匹配过程中，主串中的第i 个字符与模式中的第j个字符等时，仅需要将模式向右滑动至模式中的第k个字符和主串中的第i个字符对齐。此时，模式中头k-1个字符的子串‘p(1) p(2) p(3)…..p(k-1)’ 必定与主串中的第i 个字符之前长度为k-1 的子串 ’s(j-k&#43;1)s(j-k&#43;2)……s(j-1)’相等，由此，匹配仅需要从模式中的第 k 个字符与主串中的第 i 个字符比较起 继续进行。 若令 next[j] = k ,则next[j] 表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需要重新和主串中该字符进行的比较的位置。由此可引出模式串的next函数：<p></p><p>根据模式串P的规律： <strong> ‘p(1) p(2) p(3)…..p(k-1)’ = ‘p(j - k &#43; 1) …..p(j-1)’ </strong></p><p>由当前失配位置j(已知) ，可以归纳计算新起点k的表达式。</p><br><img style="max-width: 100%;height: auto;width: auto\9;" src="//img.reader8.net/uploadfile/jiaocheng/20140188/3029/201401301429278097.jpg" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法"><br><br><br>由此定义可推出下列模式串next函数&#20540;：<br><p><img style="max-width: 100%;height: auto;width: auto\9;" src="//img.reader8.net/uploadfile/jiaocheng/20140188/3029/201401301429278098.jpg" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法"><br></p><p><br></p><p><br></p><p>模式匹配过程:</p><p><img style="max-width: 100%;height: auto;width: auto\9;" src="//img.reader8.net/uploadfile/jiaocheng/20140188/3029/201401301429278099.jpg" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法"><br></p><p><strong>KMP算法的实现:<br></strong></p><p><strong></strong></p><p>第一步，先把模式T所有可能的失配点j所对应的next[j]计算出来；</p><p>第二步：执行定位函数Index_kmp（与BF算法模块非常相&#20284;）</p><textarea readonly name="code" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法">Pj 则表明在模式串中：</p><p> <strong>‘P(1) ….. P(k)’ <img style="max-width: 100%;height: auto;width: auto\9;" src="//img.reader8.net/uploadfile/jiaocheng/20140188/3029/201401301429278100.jpg" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法"> </strong><strong>‘P(j - k &#43; 1) ….. P(j)’ </strong><br> 此时可把next函数&#20540;的问题看成是一个模式匹配的问题，整个模式串即是主串又是模式串，<br> 而当前匹配的过程中，已有：</p><p> Pj-k&#43;1 = P1， Pj-k&#43;2 = P2，... Pj-1 = Pk-1.<br> 则当Pk<img style="max-width: 100%;height: auto;width: auto\9;" src="//img.reader8.net/uploadfile/jiaocheng/20140188/3029/201401301429278100.jpg" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法">Pj时应将模式向右滑动至以模式中的第next[k]个字符和主串中的第 j 个字符相比较。<br> 若next[k] = k`,且Pj= Pk`, 则说明在主串中的第j&#43;1 个字符之前存在一个长度为k` (即next[k])的最长子串，和模式串<br> 从首字符其长度为看k`的子串箱等。即<br> <strong>‘P(1) ….. P(k`)’ = </strong><strong>‘P(j - k` &#43; 1) ….. P(j)’ </strong><br> 也就是说next[j&#43;1] = k` &#43;1 即<br> next[j&#43;1] = next[k] &#43; 1<br> 同理，若Pj <img style="max-width: 100%;height: auto;width: auto\9;" src="//img.reader8.net/uploadfile/jiaocheng/20140188/3029/201401301429278100.jpg" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法">Pk` ,则将模式继续向右滑动直至将模式串中的第next[k`]个字符和Pj对齐，<br> ... ,一次类推，直至Pj和模式中某个字符匹配成功或者不存在k`(1&lt; k` &lt; j)满足，则:<br> next[j&#43;1] =1;</p><p> <img style="max-width: 100%;height: auto;width: auto\9;" src="//img.reader8.net/uploadfile/jiaocheng/20140188/3029/201401301429278101.jpg" alt="数据结构- 串的模式匹配算法：BF跟 KMP算法"></p><p><br></p><p></p><textarea readonly name="code" style="color:rgb(51,51,51); font-family:Arial; font-size:14px; background-color:white; text-indent:6pt; line-height:18px">next 函数&#20540;究竟是什么含义，前面说过一些，这里总结。设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数&#20540;next[n],1. next[n] = 0 表示S[m]和T[1]间接比较过了，不相等，下一次比较 S[m&#43;1] 和T[1]2. next[n] =1 表示比较过程中产生了不相等，下一次比较 S[m] 和T[1]。3. next[n] = k &gt;1 但k&lt;n, 表示,S[m]的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较S[m]和T[k]相等吗？4. 其他&#20540;，不可能。<br><p></p><p>注意：</p><p>（1）k&#20540;仅取决于模式串本身而与相匹配的主串无关。</p><p>（2）k&#20540;为模式串从头向后及从j向前的两部分的最大相同子串的长度。</p><p>（3）这里的两部分子串可以有部分重叠的字符，但不可以全部重叠。</p><p>next[j]函数表征着模式P中最大相同前缀子串和后缀子串（真子串）的长度。</p><p>可见，模式中相&#20284;部分越多，则next[j]函数越大，它既表示模式T字符之间的相关度越高，也表示j位置以前与主串部分匹配的字符数越多。</p><p>即：next[j]越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低（时间效率）。</p><br><p><br></p> </p></div><div style="margin:0 auto;width:300px;height:250px;position:relative;"> <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script> <!-- 移动端全站正文 --> <ins class="adsbygoogle" style="display:block" data-ad-client="ca-pub-6147101717324856" data-ad-slot="1958144088" data-ad-format="auto"></ins> <script> (adsbygoogle = window.adsbygoogle || []).push({}); </script></div> <div class="subn-nav"><a href="//m.reader8.net">读书人网</a> ><a href="//m.reader8.net/jiaocheng/jiagousj/">软件架构设计</a></div><div class="sp-jctu"><h3><span> 热点推荐 </span></h3><ul><li><p><a href="//m.reader8.net/jiaocheng/20140619/2409674.html">关于连通图的有关问题这道题小弟我直</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140619/2409673.html">多矩形切割拼接原材料固定,该如何处</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140618/2405888.html">字符串变换有关问题</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140618/2405887.html">DFS有序数列的全排列</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140617/2401915.html">一个栈的输入序列为a,b,c,d若在入栈</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140617/2401914.html">发个算法题解决方案</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140614/2392025.html">微软谷歌的一道面试题：怎么分隔没有空</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140614/2392024.html">位图排序的有关问题</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140613/2388331.html">求解分枝定界算法解决思路</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140613/2388330.html">后缀表达式,该怎么解决</a></p></li> </ul></div><div style="display:none;"> <script> var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "//hm.baidu.com/hm.js?d6151f323a57d16696165e47eee86d53"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); </script></div> <div class="footer"><p>触屏版 | <a href="//www.reader8.net/jiaocheng/20120621/2075510.html#fromapp">电脑版</a></p><p>读书人网 m.reader8.net</p></div> <script language="javascript"> function clickme(sad){ var divobjdiv = document.getElementById("divobjdiv" + sad); if(divobjdiv.style.display =="none"){ divobjdiv.style.display ="block"; }else{ divobjdiv.style.display ="none"; } var wenzi = document.getElementById('divobjimg' + sad); if(wenzi.innerText == "收起"){ wenzi.innerText = "查看更多"; }else{ wenzi.innerText = "收起"; } } </script> <div id="back-top"><a href="#top"><span></span></a></div> </body> </html>