KMP算法中的next[i]和nextval[i]的规律回顾

雨点打透心脏的1/2处 2022-12-24 03:53 200阅读 0赞

## 一 概述 ##

KMP算法是为了优化朴素匹配模式中的主串指针回溯问题，此过程中回产生一个next\[i\]数组，而KMP优化算法是优化模式串指针的回溯问题，此过程中回产生一个nextval\[i\]数组。

## 二 KMP算法之数组之next\[i\] ##

当模式串中的第j个字符匹配失败，由前1~j-1个字符组成的串记为S，则：next\[j\] = S的最长相等前后缀长度+1。

如模式串'aababaaaba'。串的下标从1开始。

此时字符串中第一个字母a对应next\[1\] = 0 ；第二个字母a对应next\[2\] = 0+1 = 1，其中0表示第二个字母a之前的字符串中前后缀相等的情况为0；

**注意：当个字符a中是不存在前后缀。**

第三个字符b之前的字符串为'aa'存在相同的前缀和后缀'a'，所以next\[2\] = 1 + 1 = 2。

第四个字符a之前存在的字符串为'aab'，不存在相同的前后缀，所以next\[3\] = 0 + 1 = 1。

第五个字符b之前存在的字符串为'aaba'，存在最长的相同前后缀'a'，所以next\[4\] = 1 + 1 = 2。

第六个字符a之前存在的字符串为'aabab'，不存在相同的前后缀，所以next\[5\] = 0 + 1 = 1。

第七个字符a之前存在的字符串为'aababa'，存在最长的相同前后缀为'a'，所以next\[6\] = 1 + 1 = 2。

第八个字符a之前存在的字符串为'aababaa'，存在最长的相同前后缀'aa'，所以next\[7\] = 2 + 1 = 3。

第九个字符b之前存在的字符串为'aababaaa'，存在最长的相同前后缀'aa'，所以next\[8\] = 2 + 1 = 3。

第十个字符a之前存在的字符串为'aababaaab'，存在最长的相同前后缀为'aab' 所以next\[9\] = 3 + 1 = 4。

## 三 KMP算法优化后的数组nextval\[i\] ##

**1. KMP算法会存在的不足：**

主串为gogoodgooglegooglo而模式串为google时，当比对到以下情况：

当比对到模式串google中的第二个g同gogoodgooglegooglo中的d对应上时，将模式串中的google中的第一个g移动到与gogoodgooglegooglo中d的对应位置。

由于第一次中已经知道了d与g是不相同的，所以这种比较是多余的，所以通过nextval\[i\]对KMP算法进行优化。

如模式串'aababaaaba'。

<table style="width:400px;"> 
 <tbody> 
  <tr> 
   <td>序号j</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td>7</td> 
   <td>8</td> 
   <td>9</td> 
   <td>10</td> 
  </tr> 
  <tr> 
   <td>模式串</td> 
   <td>a</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>a</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
  </tr> 
  <tr> 
   <td>next[i]</td> 
   <td>0</td> 
   <td>1</td> 
   <td>2</td> 
   <td>1</td> 
   <td>2</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>3</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>nextval[i]</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

KMP算法优化：当子串和模式串不匹配时nextval\[j\] = j；

**2. nextval数组的求法**

先算出next数组，先令nextval\[1\] = 0；

for(int j = 2; j <= T.length; j++) {
        if(T.ch[next[i]] == T.ch[i])
            nextval[j] = nextval[next[j]];
        else 
            nextval[j] = next[j];
    }

**1.** 对于第一个字符'a'的nextval\[1\] = 0；

对于第二个字符'a'的next\[2\] = 1，所以对应序号为1的元素'a'，根据

if(T.ch[next[i]] == T.ch[i])
    nextval[j] = nextval[next[j]];

将nextval\[1\]赋值给nextval\[2\]；

**2.** 对于第三个字符'b'的next\[3\] = 2，所以对应序号为2的元素'b'，根据

if(T.ch[next[i]] != T.ch[i])
    nextval[j] = next[j];

所以将next\[3\]赋值给nextval\[3\]；

由此同理可得，最后的结果如下：

<table style="width:400px;"> 
 <tbody> 
  <tr> 
   <td>序号j</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td>7</td> 
   <td>8</td> 
   <td>9</td> 
   <td>10</td> 
  </tr> 
  <tr> 
   <td>模式串</td> 
   <td>a</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>a</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
  </tr> 
  <tr> 
   <td>next[i]</td> 
   <td>0</td> 
   <td>1</td> 
   <td>2</td> 
   <td>1</td> 
   <td>2</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>3</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>nextval[i]</td> 
   <td>0</td> 
   <td>0</td> 
   <td>2</td> 
   <td>0</td> 
   <td>2</td> 
   <td>0</td> 
   <td>0</td> 
   <td>3</td> 
   <td>2</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

此处总结了KMP算法的next\[\]和nextval\[\]的计算，后续有所优化继续补充。