算法——KMP匹配算法

        在进行字符串匹配的时候，我们很容易想到将两个字符串进行遍历比较，即暴力匹配，虽然这个算法比较容易想，但是它会进行许许多多无意义的比较，浪费了时间，时间复杂度为O（m*n），今天我们要讲的是另一种算法——KMP匹配算法，它的时间复杂度为O（m+n）。

一、前缀表、前缀、后缀

        前缀：从字符串第一个字符开始，不包含最后一个字符的所有连续子串。

例：s=“ababc”

它的前缀有a、ab、aba、abab。

        后缀：从字符串最后一个字符结束，不包含第一个字符的所有连续子串。

例：s=“ababc”

它的后缀有c、bc、abc、babc。

        前缀表：计算每个子串的最长相等前后缀的长度，将结果顺序存储在数组中，该数组就是前缀表。

例：s=“ababc”，它的前缀表为prefix = [0, 0, 1, 2, 0]

分析：s的子串有‘a’，‘ab’，‘aba’，‘abab’，‘ababc’

'a'：该子串没有前后缀，故最长相等前后缀的长度为0，（由此得出前缀表第一位必为0）

'ab'：该子串前缀为a，后缀为b，不相等，故为0

'aba'：该子串前缀为a、ab，后缀为a、ba，最长相等前后缀为1

'abab'：前缀为a、ab、aba，后缀为b、ab、bab，最长相等前后缀是ab，故为2

'ababc'：显然为0

故前缀表为prefix = [0, 0, 1, 2, 0]

二、next数组

        next数组：前缀表的变形，主要有两种

• 变形1：前缀表整体减1（最常用）
• 变形2：前缀表整体右移，首位置为-1（后面以变形2讲解）

        两种变形核心是等价的。

例，prefix=[0,0,1,2,0]

那对应的next数组为：next=[ -1, 0, 0, 1, 2]

由于prefix第一位一定为0，故next数组第一位一定是-1，第二位一定是0

三、KMP匹配算法的过程及实现

3.1匹配过程

例，主串S = “abababc”，模式串P = “ababc”

匹配过程：

1.先求出P的next数组next = [ -1, 0, 0, 1, 2]

2.开始一一匹配

  a b a b a b c

   |  |  |  | X

  a b a b c

匹配到第五个时，匹配失败。

此时，如果是暴力匹配，那么P会从S的下标1开始重新匹配

但是KMP算法是

S保持当前位置不动，即下标4，将next数组中第五个数字2作为P此时要与S比较的下标，

即

  a b a b a b c

         |  |

        a b a b a 

3.后续正常匹配，如果匹配失败就继续使用KMP算法

4.最终，未找到子串就返回-1，匹配成功就将第一个找到的子串的第一个字符的下标返回

3.2代码实现

​
// 获取next数组
void getNext(int* next, string s)
{
int len = s.length();
if (len == 1)
return new int(-1); // 长度为1,就返回一个[-1]

next = new int[len];
next[0] = -1;
next[1] = 0;

int i = 2; cn = 0; // cn为当前要和前一个字符比对的下标，表示当前最长相等前缀的末尾位置
while(i < len)
{
if (s[i-1] == s[cn])
next[i++] = ++cn;
else if (cn > 0)
cn = next[cn];
else
next[i++] = 0;
}
}

​

// c++

// KMP匹配算法
int KMP(string s1, string s2)
{
int len1 = s1.length();
int len2 = s2.length();
int x = 0; // s1当前比较的下标
int y = 0; // s2当前比较的下标
int next[] = getNext(s2, len2); // 获取next数组

while( x < len1 && y < len2)
{
if (s1[x] == s2[y])
{
x++;
y++;
}
else if (y == 0) // P的第一个字符就匹配失败
{
x++;
}
else
{
y = next[y]; // 将P回退到next数组对应的值的下标
}
}
return y == len2 ? x-y : -1;
}

总结

        KMP算法是一种高效的匹配方法，希望本文能让你轻松地理解KMP算法的应用。