【考研408】kmp算法手算next和nextval数组

悠悠 2022-08-28 05:41 266阅读 0赞

首先要了解 最长相等前后缀，比如串ababa，它的最长相等前后缀就是aba。

## 手算next数组： ##

例如：求串 a b c a c 的next数组，首先画一个表格

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>编号</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>串(S)</td> 
   <td>a</td> 
   <td>b</td> 
   <td>c</td> 
   <td>a</td> 
   <td>c</td> 
  </tr> 
  <tr> 
   <td>部分匹配值(PM)</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>1</td> 
   <td> <p>0</p> </td> 
  </tr> 
 </tbody> 
</table>

部分匹配值就是 最长相等前后缀的长度

next数组就是把所有的PM的值向右移一位，第一位补-1，也就是

**-1 0 0 0 1**

再加1

**\[next\] 0 1 1 1 2**

这里需要注意的一个点是：next数组可以从-1开始，也可以从0开始(两个都对)。如果题目要求从0开始，那么直接对刚刚求得的-1开始的next数组每个数都+1就OK。

如果题目给的***字符串的下标i是从0开始的，那么next数组就是从-1开始的***；如果***字符串下标是从1开始的，那么next数组就是从0开始的。***比如本题，字符串编号是从1开始的，那么最后算出来的next数组应该从0开始。

## 手算nextval数组： ##

在next数组的基础上手算nextval数组：

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>编号</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>S</td> 
   <td>a</td> 
   <td>b</td> 
   <td>c</td> 
   <td>a</td> 
   <td>c</td> 
  </tr> 
  <tr> 
   <td>next</td> 
   <td>0</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>nextval</td> 
   <td>0</td> 
   <td>1</td> 
   <td>1</td> 
   <td>0</td> 
   <td>2</td> 
  </tr> 
 </tbody> 
</table>

首先编号为1的字符的nextval值是0，这是规定的。

然后算编号为2的字符的nextval值，先看其next值，为1。那么，找到编号为1的字符，为a。比较a和我们当前算的编号为2的字符b，两者*不同* ，直接把编号为2的 *next的值落到下面* 的nextval

再算编号为3的，和上面同理，先看next的值是1，找编号1对应的字符，即a。还是和当前字符c*不同*，直接把 *next的值落到下面*

再算编号为4的，看它的next值是1，找编号1对应的字符，即a。和当前字符*相同*了，那么直接把编号为1的 *nextval复制* 到当前nextval。

最后算编号5的nextval，和上面方法同理，为2.

总结一条口诀，相同用底下，不同用上面。