<div class="blogpost-body" id="cnblogs_post_body">
<p>节选自 https://www.cnblogs.com/zhangtianq/p/5839909.html</p>
<p>字符串匹配 KMP O(m+n）</p>
<p>O原来的暴力算法 当不匹配的时候</p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-1e29dab71739ea9a3f0ead941b951d6e"></p>
<p><span style="color:#333333;font-family:Arial;font-size:14px;">尽管之前文本串和模式串已经分别匹配到了S[9]、P[5]，但因为S[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，从而让S[5]跟P[0]匹配</span></p>
<p> </p>
<p style="font-size:14px;color:#333333;font-family:Arial;"> 而S[5]肯定跟P[0]失配。为什么呢？因为在之前第4步匹配中，我们已经得知S[5] = P[1] = B，而P[0] = A，即P[1] != P[0]，故S[5]必定不等于P[0]，所以回溯过去必然会导致失配。那有没有一种算法，让i 不往回退，只需要移动j 即可呢？</p>
<p style="font-size:14px;color:#333333;font-family:Arial;"> 答案是肯定的。这种算法就是本文的主旨KMP算法，它利用之前已经部分匹配这个有效信息，保持i 不回溯，通过修改j 的位置，让模式串尽量地移动到有效的位置。</p>
<div>
</div>
<p><span style="color:#333333;font-family:Arial;font-size:14px;"> </span></p>
<p><span style="color:#333333;font-family:Arial;font-size:14px;"><span style="color:#333333;font-family:Arial;font-size:14px;text-align:left;">假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置</span></span></p>
<ul style="margin-left:30px;color:#333333;font-family:Arial;font-size:14px;text-align:left;"><li style="margin-left:0px;">如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；</li><li style="margin-left:0px;">如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。</li></ul>
<p><span style="color:#333333;font-family:Arial;font-size:14px;">next[j]表示模式串前j-1个字符组成的子串，前缀和后缀相同的最长的长度</span></p>
<p><span style="color:#333333;font-family:Arial;font-size:14px;"><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-0f7faf3d04a370c849f4940453c91b68"><br></span></p>
<p><span style="color:#333333;font-family:Arial;font-size:14px;"> </span></p>
<p><span style="color:#333333;font-family:Arial;font-size:14px;"> </span></p>
<p> </p>
<p style="font-size:14px;color:#333333;font-family:Arial;">计算next 数组的方法可以采用递推：</p>
<ul style="margin-left:30px;font-size:14px;color:#333333;font-family:Arial;line-height:26px;"><li style="margin-left:0px;"><span style="font-family:'Comic Sans MS';">1</span>. 如果对于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于next[j] = k。</li></ul>
<ul style="margin-left:30px;font-size:14px;color:#333333;font-family:Arial;line-height:26px;"><li style="margin-left:0px;">2.已知next [0, ..., j]，如何求出next [j + 1]呢？</li></ul>
<p style="font-size:14px;color:#333333;font-family:Arial;"> 对于P的前j+1个序列字符：</p>
<ul style="margin-left:30px;font-size:14px;color:#333333;font-family:Arial;line-height:26px;"><li style="margin-left:0px;">若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1；</li><li style="margin-left:0px;">若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]，则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀"p0 p1, …, pk-1 pk"跟后缀“pj-k pj-k+1, …, pj-1 pj"相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么这个t+1 便是next[ j+1]的值，此相当于利用已经求得的next 数组（next [0, ..., k, ..., j]）进行P串前缀跟P串后缀的匹配。</li></ul>
<div style="font-size:14px;color:#333333;font-family:Arial;line-height:26px;">
<div>
<div>
那
<span style="color:#ff0000;">为何递归前缀索引k = next[k]，就能找到长度更短的相同前缀后缀呢</span>？这又归根到next数组的含义。
<span style="font-family:'Comic Sans MS';">我们拿前缀 p0 pk-1 pk 去跟后缀pj-k pj-1 pj匹配，如果pk 跟pj 失配，下一步就是用p[next[k]] 去跟pj 继续匹配，如果p[ next[k] ]跟pj还是不匹配，则需要寻找长度更短的相同前缀后缀，即下一步用p[ next[ next[k] ] ]去跟pj匹配</span>。此过程相当于模式串的自我匹配，所以不断的递归k = next[k]，直到要么找到长度更短的相同前缀后缀，要么没有长度更短的相同 |
|
转播
