KMP算法通俗理解

客官°小女子只卖身不卖艺 2022-06-13 00:26 182阅读 0赞

# 有关字符串的基本知识 #

串（string或字符串）是由零个或多个字符组成的有限序列，一般记为![这里写图片描述][20160420204547026] 其中s是串的名，用单引号括起来的字符序列是串的值；ai（1<=i<=n）可以是字母、数值或其他字符；串中字符的数组 n称为串的长度。零个字符的串称为空串，它的长度为0

串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

下面主要说一下串的模式匹配算法

# 传统的串匹配法 #

算法的基本思想是：从主串S的第pos个字符起和模式的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为零。   
此算法在最坏情况下的时间复杂度为O(m\*n)

# 模式匹配的一种改进算法（KMP算法） #

## 网上一比较易懂的讲解 ##

[字符串匹配的KMP算法][KMP]

字符串匹配是计算机的基本任务之一。   
举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串”ABCDABD”？

许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。

下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。   
1.![这里写图片描述][20160420212633989]

首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。   
2.   
![这里写图片描述][20160420212704099]   
因为B与A不匹配，搜索词再往后移。   
3.![这里写图片描述][20160420213627024]

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。   
4.![这里写图片描述][20160420213638462]

接着比较字符串和搜索词的下一个字符，还是相同。   
5.![这里写图片描述][20160420213652079]

直到字符串有一个字符，与搜索词对应的字符不相同为止。   
6.   
![这里写图片描述][20160420213702016]   
这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。   
7.   
![这里写图片描述][20160420213720947]   
一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。   
8.   
![这里写图片描述][20160420213745103]   
怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。   
9.   
![这里写图片描述][20160420213755650]   
已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此按照下面的公式算出向后移动的位数：   
　　移动位数 = 已匹配的字符数 - 对应的部分匹配值   
因为 6 - 2 等于4，所以将搜索词向后移动4位。   
10.   
![这里写图片描述][20160420213817713]   
因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。   
11.   
![这里写图片描述][20160420213841135]   
因为空格与A不匹配，继续后移一位。   
12.   
![这里写图片描述][20160420213851619]   
逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。   
13.   
![这里写图片描述][20160420213904284]   
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。   
14.   
![这里写图片描述][20160420213915760]   
下面介绍《部分匹配表》是如何产生的。   
首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。   
15.   
![这里写图片描述][20160420213927972]   
“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，   
　　－　“A”的前缀和后缀都为空集，共有元素的长度为0；   
　　－　“AB”的前缀为\[A\]，后缀为\[B\]，共有元素的长度为0；   
　　－　“ABC”的前缀为\[A, AB\]，后缀为\[BC, C\]，共有元素的长度0；   
　　－　“ABCD”的前缀为\[A, AB, ABC\]，后缀为\[BCD, CD, D\]，共有元素的长度为0；   
　　－　“ABCDA”的前缀为\[A, AB, ABC, ABCD\]，后缀为\[BCDA, CDA, DA, A\]，共有元素为”A”，长度为1；   
　　－　“ABCDAB”的前缀为\[A, AB, ABC, ABCD, ABCDA\]，后缀为\[BCDAB, CDAB, DAB, AB, B\]，共有元素为”AB”，长度为2；   
　　－　“ABCDABD”的前缀为\[A, AB, ABC, ABCD, ABCDA, ABCDAB\]，后缀为\[BCDABD, CDABD, DABD, ABD, BD, D\]，共有元素的长度为0。   
16.   
![这里写图片描述][20160420214001604]   
“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。

--------------------

## 小例子 ##

求字符串 ‘ababaabab’的next和nextval，结果如下

--------------------

## （1）计算next ##

> 计算next的时候需要遵循的规则如下
> 
> > A、 j = 0 next\[j\] = 0   
> > B、如果存在 Max\{ k | k 属于 （1，j-1） 且‘P1…Pk-1’= ‘Pj-k+1…Pj-1’ \} （next\[j\] = k）   
> > C、其他情况 next\[j\] = 1

<table style="width:720px; border-collapse:collapse; border-spacing:0px; border:1px solid rgb(238,238,238); color:rgb(63,63,63); font-family:&quot;microsoft yahei&quot;; font-size:15px"> 
 <thead style=""> 
  <tr style=""> 
   <th align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> j</th> 
   <th align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ( 1, k-1 )</th> 
   <th align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> str(1,k-1)</th> 
   <th style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ( j-k+1 , j-1 )</th> 
   <th style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> str( j-k+1, j-1)</th> 
   <th style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 规则</th> 
   <th style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> next[ j ]</th> 
  </tr> 
 </thead> 
 <tbody style=""> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 2</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> NULL</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> NULL</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> NULL</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> NULL</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> C</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 1</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 3</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,1)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> a</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (2,2)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> b</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> C</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 1</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 4</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,2)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (2,3)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 4</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,1)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> a</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (3,3)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> a</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> B</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 2</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 5</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,3)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> aba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (2,4)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> bab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 5</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,2)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (3,4)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> B</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 3</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 6</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,4)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> abab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (2,5)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> baba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 6</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,3)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> aba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (3,5)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> aba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> B</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 4</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 7</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,5)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ababa</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (2,6)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> babaa</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 7</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,4)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> abab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (3,6)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> abaa</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 7</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,3)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> aba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (4,6)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> baa</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 7</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,2)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (5,6)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> aa</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 7</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,1)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> a</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (6,6)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> a</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> B</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 2</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 8</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,6)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ababaa</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (2,7)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> babaab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 8</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,5)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ababa</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (3,7)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> abaab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 8</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,4)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> abab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (4,7)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> baab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 8</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,3)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> aba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (5,7)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> aab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 8</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,2)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (6,7)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> B</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 3</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 9</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,7)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ababaab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (2,8)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> babaaba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 9</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,6)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ababaa</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (3,8)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> abaaba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 9</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,5)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> ababa</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (4,8)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> baaba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 9</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,4)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> abab</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (5,8)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> aaba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
  <tr style=""> 
   <td align="left" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 9</td> 
   <td align="right" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (1,3)</td> 
   <td align="center" style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> aba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> (6,8)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> aba</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> B</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> 4</td> 
  </tr> 
 </tbody> 
</table>

--------------------

## （2）计算nextval ##

nextval\[i\]的求解需要比较s中next\[i\]所在位置的字符是否与s\[i\]的字符一致，如果一致则用s\[next\[i\]\]的nextval的值作为nextval\[i\]，如果不一致，则用next\[i\]做为nextval\[i\]。

--------------------

## 代码 ##

该代码参考 [数据结构][Link 1]（[C语言][C]版） 严蔚敏 吴伟民 编著。。。

/** * @filename kmp.cc * @Synopsis KMP algorithm * @author XIU * @version 1 * @date 2016-04-21 */
    // 此代码中所用的数组，或者是字符串都是从下标1开始
    
    #include<iostream>
    #include<string.h>
    
    using namespace std;
    
    /* ============================================================================*/
    /** * @Synopsis the next index data of the model string s_mode * * @Param s_mode: the string * @Param next : the next array * @Param len : the length of the string */
    /* ============================================================================*/
    void get_next( string s_mode, int *next, int len )
    {
        int i = 1;
        int j = 0;
        next[1] = 0;
    
        //cout << len << endl;
        while( i<len )
        {
    
            if( j==0 || s_mode[i] == s_mode[j] )
            {
                ++i;
                ++j;
                if( i>len ) break;
                next[i] = j;
                if( j>len ) break;
                //下面的是修正的next算法（nextval）。
                /* if( s_mode[i] != s_mode[j]) next[i] = j; else next[i] = next[j]; */
            }
            else
            {
                j = next[j];
            }
        }
        for( int i=1; i<len; i++ )
        {
            cout << next[i] << " ";
        }
    
        cout << endl; 
    
    }
    
    /* ============================================================================*/
    /** * @Synopsis 利用模式串s_mode中的next函数求s_model在主串 s_primary中第pos个字符之后的位置 * * @Param s_primary * @Param s_mode * @Param pos * @Param next * * @Returns */
    /* ============================================================================*/
    int Index_KMP( string s_primary, string s_mode, int pos, int *next )
    {
        int i = pos;
        int j = 1;
    
        int len_p = s_primary.size();
        int len_m = s_mode.size();
    
        while( i < len_p && j < len_m )
        {
    
            if( j == 0 || s_primary[i] == s_mode[j] )
            {
                ++i;
                ++j;
            }
            else
                j = next[j];
        }
    
        if( j >= len_m )
            return i - len_m;
        else
            return 0;
    }
    
    /* ============================================================================*/
    /** * @Synopsis output function to check the result * * @Param s_primary * @Param s_mode * @Param len * @Param next * @Param index */
    /* ============================================================================*/
    void output( string s_primary, string s_mode, int len, int *next, int index )
    {
        cout << "s_primary = " << s_primary << endl;
        cout << "s_mode = " << s_mode << endl;
    
        for( int i=1; i<len; i++ )
        {
            cout << next[i] << " ";
        }
    
        cout << endl; 
    
        cout << "index = " << index << endl;
    
    }
    int main()
    {
        string s_primary = " acabaabaabcacaabc";
        string s_mode    = " abaabcac";
        int len = s_mode.size() ;
    
        int *next = new int[len];
    
        get_next( s_mode, next, len );
    
        int tmp = Index_KMP( s_primary, s_mode, 1, next );
    
        output( s_primary, s_mode, len, next, tmp );
    
    
        delete [] next;
        return 0;
    }
     
      
       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
       30
       31
       32
       33
       34
       35
       36
       37
       38
       39
       40
       41
       42
       43
       44
       45
       46
       47
       48
       49
       50
       51
       52
       53
       54
       55
       56
       57
       58
       59
       60
       61
       62
       63
       64
       65
       66
       67
       68
       69
       70
       71
       72
       73
       74
       75
       76
       77
       78
       79
       80
       81
       82
       83
       84
       85
       86
       87
       88
       89
       90
       91
       92
       93
       94
       95
       96
       97
       98
       99
       100
       101
       102
       103
       104
       105
       106
       107
       108
       109
       110
       111
       112
       113
       114
       115
       116
       117
       118
       119
       120
       121
       122
       123
       124
       125
       126
       127
       128
       129
       130
       131
       132
       133
       134
       135
       136
       137
       138
       139
       140
       141
       142
       143
      
     
      
       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
       30
       31
       32
       33
       34
       35
       36
       37
       38
       39
       40
       41
       42
       43
       44
       45
       46
       47
       48
       49
       50
       51
       52
       53
       54
       55
       56
       57
       58
       59
       60
       61
       62
       63
       64
       65
       66
       67
       68
       69
       70
       71
       72
       73
       74
       75
       76
       77
       78
       79
       80
       81
       82
       83
       84
       85
       86
       87
       88
       89
       90
       91
       92
       93
       94
       95
       96
       97
       98
       99
       100
       101
       102
       103
       104
       105
       106
       107
       108
       109
       110
       111
       112
       113
       114
       115
       116
       117
       118
       119
       120
       121
       122
       123
       124
       125
       126
       127
       128
       129
       130
       131
       132
       133
       134
       135
       136
       137
       138
       139
       140
       141
       142
       143

--------------------

参考网址   
【1】字符串匹配的KMP算法 - 阮一峰的网络日志   
[http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt\_algorithm.html][KMP]  
【2】KMP算法详解 - joylnwang的专栏 - 博客频道 - CSDN[.NET][]   
[http://blog.csdn.net/joylnwang/article/details/6778316][http_blog.csdn.net_joylnwang_article_details_6778316]   
【3】经典算法研究系列：六、教你初步了解KMP算法、updated - 结构之法 算法之道 - 博客频道 - CSDN[.net][.NET]   
[http://blog.csdn.net/v\_JULY\_v/article/details/6111565][http_blog.csdn.net_v_JULY_v_article_details_6111565]

[20160420204547026]: /images/20220613/7dc4f5a0b1e5416daa8fce8c511ad360.png
[KMP]: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
[20160420212633989]: /images/20220613/1cd1cdf8514d4f35a44074ef67604db8.png
[20160420212704099]: /images/20220613/c509e9fd85454e3b9f5dced30cfaaa59.png
[20160420213627024]: /images/20220613/cf4e8cc423a54c87bd290b8cfc4098cd.png
[20160420213638462]: /images/20220613/a1eb12046fcb49a48e55f836ee832f82.png
[20160420213652079]: /images/20220613/7933b2830a2440e08aa7c3cac672963c.png
[20160420213702016]: /images/20220613/92252fbb0b154feb945d29291a47c49a.png
[20160420213720947]: /images/20220613/d0f9b49de91446af91757346a6657037.png
[20160420213745103]: /images/20220613/96fa222f7b3d4d839b3c2f952bcd7c89.png
[20160420213755650]: /images/20220613/53f71059917d40a4bb5962c7eb97493a.png
[20160420213817713]: /images/20220613/d4c5894c50bb49d98fe3d569097391dd.png
[20160420213841135]: /images/20220613/058374196eee4fef8a9017598c6f02ce.png
[20160420213851619]: /images/20220613/0d2cca4f961d405d9c8e6291d8fc5863.png
[20160420213904284]: /images/20220613/22f9db1cc233473bbd4e9d40020060b3.png
[20160420213915760]: /images/20220613/cae11737736340f690d9823559e54cca.png
[20160420213927972]: /images/20220613/017f0da0e4b245378663959b907b4262.png
[20160420214001604]: /images/20220613/bda8e3b5931d4b84b5938efcdb0da3b7.png
[Link 1]: http://lib.csdn.net/base/datastructure
[C]: http://lib.csdn.net/base/c
[.NET]: http://lib.csdn.net/base/dotnet
[http_blog.csdn.net_joylnwang_article_details_6778316]: http://blog.csdn.net/joylnwang/article/details/6778316
[http_blog.csdn.net_v_JULY_v_article_details_6111565]: http://blog.csdn.net/v_JULY_v/article/details/6111565