扩展 KMP

灰太狼 2023-06-01 06:11 73阅读 0赞

*  扩展 KMP
    
     *  一：算法流程
     *  二：代码

# 扩展 KMP #

[来源][Link 1]  
问题定义：给定两个字符串 S 和 T（长度分别为 n 和 m），下标从 0 开始，定义 **extend\[i\]** 等于 S\[i\]... S\[n-1\] 与 T 的最长相同前缀的长度，求出所有的 **extend\[i\]**。举个例子，看下表：

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center;">i</th> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center;">S</td> 
   <td>a</td> 
   <td>a</td> 
   <td>a</td> 
   <td>a</td> 
   <td>a</td> 
   <td>b</td> 
   <td>b</td> 
   <td>b</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">T</td> 
   <td>a</td> 
   <td>a</td> 
   <td>a</td> 
   <td>a</td> 
   <td>a</td> 
   <td>c</td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td style="text-align:center;"><strong>extend[i]</strong></td> 
   <td>5</td> 
   <td>4</td> 
   <td>3</td> 
   <td>2</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

为什么说这是 KMP 算法的扩展呢？显然，如果在 S 的某个位置 i 有 **extend\[i\]** 等于 m，则可知在 S 中找到了匹配串 T，并且匹配的首位置是 i。而且，扩展 KMP 算法可以找到 S 中所有 T 的匹配。接下来具体介绍下这个算法。

## 一：算法流程 ##

![20180412\_01.png][20180412_01.png]  
如上图，假设当前遍历到 S 串位置 i，即 **extend\[0\]...extend\[i - 1\]** 这 i 个位置的值已经计算得到。设置两个变量，a 和 p。p 代表以 a 为起始位置的字符匹配成功的最右边界，也就是 "p = 最后一个匹配成功位置 + 1"。相较于字符串 T 得出，**S\[a...p)** 等于 **T\[0...p-a)**。

再定义一个辅助数组 **int next\[\]**，其中 **next\[i\]** 含义为：**T\[i\]... T\[m - 1\]** 与 T 的最长相同前缀长度，m 为串 T 的长度。举个例子：

![20180412\_02.png][20180412_02.png]  
S\[i\]对应 **T\[i - a\]**，如果 **i + next\[i - a\] < p**，如上图，三个椭圆长度相同，根据 next 数组的定义，此时extend\[i\] = next\[i - a\]。

（3）  
![20180412\_03.png][20180412_03.png]  
如果 **i + next\[i - a\] == p** 呢？如上图，三个椭圆都是完全相同的，**S\[p\] != T\[p - a\]且T\[p - i\] != T\[p - a\]**，但S\[p\]有可能等于 **T\[p - i\]**，所以我们可以直接从 **S\[p\]** 与 **T\[p - i\]** 开始往后匹配，加快了速度。

（4）

![20180412\_04.png][20180412_04.png]  
如果 **i + next\[i - a\] > p** 呢？那说明 **S\[i...p)与T\[i-a...p-a)** 相同，注意到 **S\[p\] != T\[p - a\]且T\[p - i\] == T\[p - a\]** ，也就是说 **S\[p\] != T\[p - i\]**，所以就没有继续往下判断的必要了，我们可以直接将 **extend\[i\]** 赋值为 **p - i**。

（5）最后，就是求解 next 数组。我们再来看下next\[i\]与extend\[i\]的定义：

*  **ext\[i\]** ： **T\[i\]...T\[m - 1\]** 与 T 的最长相同前缀长度；
 *  **extend\[i\]**： **S\[i\]...S\[n - 1\]** 与 T 的最长相同前缀长度。  
    恍然大悟，求解next\[i\]的过程不就是 T 自己和自己的一个匹配过程嘛，下面直接看代码。

## 二：代码 ##

#include <iostream> #include <string> using namespace std; /* 求解 T 中 next[]，注释参考 GetExtend() */ void GetNext(string & T, int & m, int next[]) { int a = 0, p = 0; next[0] = m; for (int i = 1; i < m; i++) { if (i >= p || i + next[i - a] >= p) { if (i >= p) p = i; while (p < m && T[p] == T[p - i]) p++; next[i] = p - i; a = i; } else next[i] = next[i - a]; } } /* 求解 extend[] */ void GetExtend(string & S, int & n, string & T, int & m, int extend[], int next[]) { int a = 0, p = 0; GetNext(T, m, next); for (int i = 0; i < n; i++) { if (i >= p || i + next[i - a] >= p) // i >= p 的作用：举个典型例子，S 和 T 无一字符相同 { if (i >= p) p = i; while (p < n && p - i < m && S[p] == T[p - i]) p++; **extend[i]** = p - i; a = i; } else **extend[i]** = next[i - a]; } } int main() { int next[100]; int extend[100]; string S, T; int n, m; while (cin >> S >> T) { n = S.size(); m = T.size(); GetExtend(S, n, T, m, extend, next); // 打印 next cout << "next: "; for (int i = 0; i < m; i++) cout << next[i] << " "; // 打印 extend cout << "\nextend: "; for (int i = 0; i < n; i++) cout << **extend[i]** << " "; cout << endl << endl; } return 0; }

数据测试如下：

aaaaabbb
    aaaaac
    next:   6 4 3 2 1 0
    extend: 5 4 3 2 1 0 0 0
    
    abc
    def
    next:   3 0 0
    extend: 0 0 0

转载于:https://www.cnblogs.com/tttfu/p/11309577.html

[Link 1]: https://subetter.com/algorithm/extended-kmp-algorithm.html
[20180412_01.png]: https://subetter.com/images/figures/20180412_01.png
[20180412_02.png]: https://subetter.com/images/figures/20180412_02.png
[20180412_03.png]: https://subetter.com/images/figures/20180412_03.png
[20180412_04.png]: https://subetter.com/images/figures/20180412_04.png