KMP 算法

介绍

KMP 算法是一种改进的字符串匹配算法。

KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

具体实现就是通过一个 next() 函数实现，函数本身包含了模式串的局部匹配信息。

KMP 算法的时间复杂度 O(m+n) 。

详解

详见代码：Code

核心代码：

void pre()//求 P 数组（即 next 数组） 
{
    P[1]=0;//记得本题中字符串从 1 开始 
    int j=0;
    for(int i=1;i<m;i++)
    {
        while(j>0 && B[j+1]!=B[i+1])
            j=P[j];
        if(B[j+1]==B[i+1])
            j++;
        P[i+1]=j;
    }
}

一、KMP 算法

目的：找到模式串 B 在原字符串 A 中第一次出现的位置。

n、m 分别为 A 和 B 的长度

流程：

[STEP 1]
if A[i+1]==B[j+1]
    i++,j++;

   i
A: ababcabcacbab
B: abcac
   j

[STEP 2]
if A[i+1]==B[j+1]
    i++,j++;

    i
A: ababcabcacbab
B: abcac
    j

[STEP 3]
if A[i+1]!=B[j+1]
    j=next[j];

    i
A: ababcabcacbab
B:   abcac
    j

if A[i+1]==B[j+1]（如果不等于的话就只加i）
    i++,j++;

     i
A: ababcabcacbab
B:   abcac
     j

[STEP 4]
略

二、`next` 数组的求法

next 数组记录最长相同前缀后缀

具体来说，就是 next 数组负责记录 B 字符串（也就是待查找子串）每个位置的属性，next[i] 记录 B[0…i] 中的前缀和后缀最长有多少一样的，比如 abcdab 中，[ab]cde[ab] 最长相同前缀后缀为 ab。

例：

a   next[0]=0（注意！这是默认值 0 ，不是 1 ）
ab  next[1]=0（a!=b）
abc next[2]=0（a!=c）
abca    next[3]=1（a==a）
abcab   next[4]=2（ab==ab）
abcabc  next[5]=3（abc==abc）

next 数组的操作与 KMP 类似

例：abcaba

初始状态
   0
   i
B: abcaba
  j

if B[j+1]!=B[i+1]
    i++;

   00
    i
B: abcaba
  j

if B[j+1]!=B[i+1]
    i++;

   000
     i
B: abcaba
  j

if B[j+1]==B[i+1]
    i++,j++;

   0001
      i
B: abcaba
   j

if B[j+1]==B[i+1]
    i++,j++;

   00012
       i
B: abcaba
    j

if B[j+1]!=B[i+1]
    j=next[j];

if B[j+1]==B[i+1]
    i++,j++;

   000121
        i
B: abcaba
   j

注：部分资料来源于百度百科

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

KMP 算法

介绍

详解

一、KMP 算法

二、next 数组的求法

二、`next` 数组的求法