串匹配（无回溯匹配）KMP 算法的代码实现（python语言）

àì夳堔傛蜴生んèń 2022-05-24 10:13 156阅读 0赞

- KMP的精髓是开发了一套分析和记录模式串信息的机制（和算法），这里为p_next表
     - KMP的基本思想是匹配中不回溯
     - p_next中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度

> 例如，对于”aba”，它的前缀集合为\{”a”, ”ab”\}，后缀集合为\{”ba”, ”a”\}。两个集合的交集为\{”a”\}，那么长度最长的元素就是字符串”a”，长 度为1，所以它在p\_next表中的值就是1。  
> 再例如：对于字符串”ababa”，它的前缀集合为\{”a”, ”ab”, ”aba”, ”abab”\}，它的后缀集合为\{”baba”, ”aba”, ”ba”, ”a”\}， 两个集合的交集为\{”a”, ”aba”\}，其中最长的元素为”aba”，长度为3，所以它在p\_next表中的值就是3。  
> 例如下表：

<table> 
 <thead> 
  <tr> 
   <th>char</th> 
   <th align="center">a</th> 
   <th align="right">b</th> 
   <th>a</th> 
   <th>b</th> 
   <th>a</th> 
   <th>b</th> 
   <th>c</th> 
   <th>a</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>index</td> 
   <td align="center">0</td> 
   <td align="right">1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>next</td> 
   <td align="center">0</td> 
   <td align="right">0</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>0</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>p_next</td> 
   <td align="center">-1</td> 
   <td align="right">0</td> 
   <td>0</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

*  具体思想：（如下图）  
    ![这里写图片描述][70]
    
    > 在主字符串”ababababca”中查找模式字符串”abababca”。如图a，如果在j处字符不匹配，那么说明主字符串i指针之前的字符和模式字符串j指针之前的这一段字符串匹配。模式串是从0到j-1，在本例中就是’ababab’,其前缀集合和后缀集合的交集的最大长度为4。所以就说主字符串中i指针之前的4位一定与模式字符串的第0到4位是相同的，及上图中的阴影部分相同。这样就可以将这些字符段的比较省略掉，具体做法就是保持i指针不动，然后将j指针指向模式字符串的next\[j-1\] = p\_next\[j\]位。简而言之，就是在i处失配，那么主字符串的前六位和模式字符串的前六位就是相同的。又因为模式字符串的前4位前缀和后4位后缀是相同的，可推得主字符串i之前的4位和模式字符串开头的前4位是相同的，那这部分就不需用再比较了。
 *  代码实现：

# 匹配函数的定义
    def matching_kmp(t, p, p_next):
        j, i = 0, 0  # i、j指针的初始化
        n, m = len(t), len(p)  # n为主字符串的长度，m为模式字符串的长度
        while j < n and i < m:  # 在i和j指针不超出t和p字符串的范围内持续执行
            if i == -1 or t[j] == p[i]:  # 遇到-1或字符相等，比较下一对字符
                j, i = j+1, i+1  # i和j指针分别后移一位
            else:  # 从p_next中取得下一字符的位置
                i = p_next[i]
        if i == m:  # 当匹配时
            return j-i  # 返回主字符串匹配的字符段的首字符
        return -1  # 不匹配返回异常值
    
    
    # 生成p_next里列表的Python函数定义
    def make_p_next(p):
        i, k, m = 0, -1, len(p)  # m赋为模式串的长度
        p_next = [-1]*m  # p_next列表的初始化
        while i < m-1:  # 指针i在模式字符串p内时持续执行
            while k >= 0 and p[i] != p[k]:  # i和k指针都在主字符串内，并且主字符串的相邻字符（即i和k所指的字符）相等时
                k = p_next[k]
            i, k = i+1, k+1  # i和k指针分别后移一位
            if p[i] == p[k]:  # 指针i和指针k所指向的值相等时
                p_next[i] = p_next[k]
            else:
                p_next[i] = k
        return p_next  # 返回p_next列表

[70]: /images/20220524/9f39b30ba4584d5d97073273edb35d90.png