KMP算法

发表于 更新于 分类于

问题引入

给出字符串str1, 字符串str2, len(str1) > len(str2), 求出str2在str1中的位置, 如果不存在输出-1;
样例1:
输入: str1 = "asfdgdg" str2 = "dg"
输出: 4
样例2: str1 = "asfdgdg" str2 = "dsg"
输出: -1

问题建模

解决的问题：判断一个字符串是否是另一个字符串的一个子串

假设str1.len = N, str2.len = M, 且(N >= M)

问题分析

很容易想到常规的解题思路，使用暴力算法，在 str1 的每一个位置进行判断。

其时间复杂度为：O(N*M)。

KMP算法

前缀等于后缀的最大长度

在理解KMP算法之前，我们需要了解前缀等于后缀的最大长度的概念，给出一个字符串str，可以得到唯一的一个前缀等于后缀的最大长度。

前缀、后缀比较容易理解，如果不考虑字符串本身，对于字符串abamaba，其前缀有a、ab、aba、abam、abama、abamab，后缀有a、ba、aba、maba、amaba、bambba。前缀与后缀相等的字符串包括a、aba。那么前缀等于后缀的最大长度的字符串为aba，最大长度为3。

获得str2的next数组

首先明确的一点是next数组长度与str2的长度相等，即为M。

next[i]：str2[0:i-1]这个字符串的 前缀等于后缀的最大长度。

默认next[0] = -1, next[1] = 0。

举个例子：求出字符串abcmabc的next数组

其结果为：

index 0 1 2 3 4 5 6
next数组值 -1 0 0 0 0 1 2


接下来讲述求解next数组的过程，当然也可以先跳过这一部分看下一节，先了解KMP算法如何通过next数组来加速匹配的过程。以字符串ababdababam为例，首先说明的是求next[i]的值需要用到next[0] ~ next[i-1]的结果，所以整个求解next数组过程就是遍历一次字符串的过程。

假设此时我们遍历到该字符串最后一个字符m的位置，我们要得到字符串ababdababa的前缀等于后缀的最大长度，从而求得next[10]的值。此时我们已经求得next[0]~next[9]的值，结果如下表。

index 0 1 2 3 4 5 6 7 8 9 10
当前子串 a ab aba abab ababd ababda ababdab ababdaba ababdabab ababdababa
next数组值 -1 0 0 1 2 0 1 2 3 4 ?

我们首先比较str[next[9]] == str[9]，发现 ‘d’ != ‘a’。接着再比较str[ next[ next[9] ] ] == str[9] –> next[next[4]] == str[9]，即比较str[2] == str[9]，发现’a’ = ‘a’，结束过程，next[10] = next[4] + 1=3，对应的前后缀为aba。

观察上述过程，可以发现首先看next[9]的位置，再看next[next[9]]的位置，如果我们得到的索引<=0，说明可以直接将next[10] = 0。

KMP算法最难理解就是上面的过程，这个需要自己仔细思考。

KMP算法过程

首先需要说明的是KMP算法的时间复杂度为O(N)，一次遍历即可完成操作。

假设str1 = dabckpabckp，str2 = abckpabca。

过程如下：

  1. 初始化指向str1位置指针i=0，指向str2位置指针j=0.
  2. 将str1[0]与str2[0]比较(因为i = 0 且 j = 0)，发现字符不相等，i++，此时i = 1。
  3. 比较str1[1]与str2[0]，字符相等，i++，j++以此类推，直到比较到i=9，j=8的时候。
  4. 发现str1[9] != str2[8]，如图1所示。
  5. 接下来调整j = next[j]，即j = next[8] = 3，如图2所示。
  6. 将str1[9]与str2[3]继续比较。
  7. 重复上述过程，最终如果全部匹配完成，说明str1包含str2。

KMP算法实现(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
	KMP算法实现 
	
*/

#include <iostream>
#include <cstring>
using namespace std;

#define MAX_LEN 10000
int next[MAX_LEN] = {0};

void getNextArray(string s);

// s1中s2作为子串的位置 
int subStringIndexof(string s1, string s2)
{
    int i1,i2=0;
    getNextArray(s2);
    for(int i = 0; i <= s2.length(); i++)
    {
        cout<<next[i]<<endl;
    } 
    while(i1 < s1.length() && i2 < s2.length())
    {
        if(s1[i1] == s2[i2])
        {
            i1++;
            i2++;
        }else if(next[i2] == -1){
            i1++;
        }else{
            i2 = next[i2];
        }
    }
    
    return i2==s2.length()?(i1-i2):-1;	
}



void getNextArray(string s)
{
    next[0] = -1;
    if(s.length() == 1) return;
    
    next[1] = 0;
    
    int i = 2;
    int cn = 0;
    while(i <= s.length())
    {
        if(s[i-1] == s[cn])
        {
            next[i++] = ++cn;
        }else if(cn > 0){
            cn = next[cn];
        }else{
            next[i++] = 0;
        }
    }
}



int main(int argc, char *argv[])
{
    string s1 = "abbbffdbbffsf";
    string s2 = "bffssbffs";
    cout<<subStringIndexof(s1,s2)<<endl;
    return 0;
}

实际应用

1. 2018校招-京东-两个子串

题目描述
给定一个字符串s, 请计算输出含有连续两个s作为子串的最短字符串。 注意两个s可能有重叠部分。例如,”ababa”含有两个”aba”.

输入描述:

输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 50),s中每个字符都是小写字母.

输出描述:

输出一个字符串,即含有连续两个s作为子串的最短字符串。

思路:
使用next数组, 求出最大前缀和后缀长度,输出即可.

牛客网题目链接

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
using namespace std;

int getNextArray(int* next,string s)
{
    next[0] = -1;
    next[1] = 0;
    int i = 2;
    int nex = 0;
    while(i <= s.length())
    {
        if(s[i-1] == s[nex])
            next[i++] = ++nex;
        else if(nex > 0){
            nex = next[nex];
        }else{
            next[i++] = 0; 
        }
    }
    return next[s.length()];
}

 
int main(int argc, char *argv[])
{
    string s;
    int next[60];
    while(cin>>s)
    {
        int max_str = getNextArray(next,s);
        cout<<s;
        for(int i = max_str; i < s.length();i++) cout<<s[i];
        cout<<endl;
    }		
    return 0;
}

2. 字符串重复问题

已知字符串是由某个子串重复的得到,如abcabcabc是由子串abc重复得到,求字符串的子串.

思路
可以使用KMP算法中的next数组,求出最大前缀长度, 原来字符串除去最大前缀剩下的部分就是要求的子串.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
using namespace std;

int getNextArray(int* next,string s)
{
    next[0] = -1;
    next[1] = 0;
    int i = 2;
    int nex = 0;
    while(i <= s.length())
    {
        if(s[i-1] == s[nex])
            next[i++] = ++nex;
        else if(nex > 0){
            nex = next[nex];
        }else{
            next[i++] = 0; 
        }
    }
    return next[s.length()];
}

 
int main(int argc, char *argv[])
{
    string s;
    int next[60];
    while(cin>>s)
    {
        for(int i = max_str; i < s.length();i++) cout<<s[i];
        cout<<endl;
    }		
    return 0;
}


3. 两个字符串改成两个二叉树

tree2在tree1中的位置

思路
将树进行序列化, 然后再使用字符串的KMP算法求解