代码随想录算法训练营第九天 | KMP

KMP

理论讲解视频：帮你把KMP算法学个通透！（理论篇）_哔哩哔哩_bilibili

代码讲解视频：帮你把KMP算法学个通透！（求next数组代码篇）_哔哩哔哩_bilibili

文章讲解：代码随想录 (programmercarl.com)

理论

解决的问题

字符串匹配。eg. 有文本串aabaabaaf，模式串aabaaf，问：在文本串种是否出现模式串？

暴力法

指针i遍历文本串，指针j遍历模式串。当j指向f、i指向b时，发现不匹配；然后整体将模式串后移一位，即：i指向文本串第二个a、j指向模式串的第一个a，然后继续匹配；然后匹配不上，整体将模式串向后移一位；…直到i指向文本串第四个字符、j指向模式串第一个a时（如下图），二者才能匹配上。

暴力法的时间复杂度为O(m*n)，分别为文本串和模式串的长度。

KMP法

指针i遍历文本串，指针j遍历模式串。当i指向的b和j指向的f不匹配时，KMP算法不是让j从头开始，而是让j跳到之前匹配过的内容，即模式串中字符b的位置，指针i不动，如下图所示。然后继续匹配。

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

前缀表

KMP算法是如何让j调到模式串中字符b的位置？即：如何知道之前匹配过哪些并且跳到那个已经匹配过的内容的后面继续开始匹配？

利用前缀表来找到之前已经匹配过的内容。

前缀表的功能？

前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

什么是前缀表？

前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

如上例，模式串中的j从f跳到了b，f前面的子串aabaa，它的后缀是aa，前缀也是aa。当j在f处不匹配时，就找f前面的子串的一个后缀是aa，找到与这个后缀相等的前缀的后面(即b)重新开始匹配。所以这里需要求的是：一个字符串的最长相等前后缀。这样，在遇到不匹配的位置的时候，就找前面这个子串的最长相等前后缀的长度(上例是2)，然后跳到下标为该长度值(即2)的位置，也就是上例中b的位置。【！前后缀相同，就不需要再匹配前缀了。】

前缀与后缀

前缀：包含首字母、不包含尾字母的所有子串。对于字符串aabaaf，其前缀为：a、aa、aab、aaba、aabaa。

后缀：包含尾字母、不包含首字母的所有子串。对于字符串aabaaf，其后缀为：f、af、aaf、baaf、abaaf。

最长相等前后缀

即：最长相等的前缀和后缀的长度。

首先逐个分析字符串“aabaaf“中的各个子串的最长相等前后缀长度都是多少：a是0，aa是1，aab是0，aaba是1，aabaa是2，aabaaf是0

这里得到一个序列：010120，就是模式串aabaaf的前缀表，那么如何利用这个前缀表来进行匹配呢？

一开始匹配时，指针i到字符b，指针j到字符f，不匹配了。就找字符b前面子串"aabaa"的最长相等前后缀是多少，也就是01012中的最大值2。这个“2”意味着“aabaa”中的后缀aa与前缀aa相等，当我们在后缀aa的后面不匹配时，就要找到与其相等的前缀的后一位置继续匹配，如下图所示。那么，与其相等的前缀的后一位置的下标就是字符串"aabaa"的最长相等前后缀的长度2，即字符b的位置。

下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。

所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

为什么j要跳到“下标为最长相等前后缀长度的位置”？因为要跳到前缀的后面，其下标就是前缀的长度(索引从0开始)。

next数组

存放前缀表，该数组告诉我们：遇到冲突时，j要回退到哪个位置。

总结

找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。

为什么要前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀。

所以要看前一位的 前缀表的数值。

前一个字符的前缀表的数值是2， 所以把下标移动到下标2的位置继续比配。

代码

前缀表即next数组的代码实现

思路

1. 初始化：指针i是后缀末尾位置；指针j是前缀末尾位置，也表示i之前(包括i)的子串的最长相等前后缀的长度；
2. 指针i遍历模式串s，【最长相等前后缀相当于拿前缀和后缀进行字符串匹配，这里的指针i的遍历相当于模拟字符串匹配时模式串的指针】
   1. 处理前后缀不相同的情况
   2. 处理前后缀相同的情况
   3. 更新next数组的值

void getNext(int* next, const string& s) {	//模式串s
    /*初始化*/
    int j = 0;	//j为前缀末尾位置，前缀从模式串首字符开始
    next[0] = 0;	//0的位置只能回退到0
    /*指针i遍历模式串s*/
    for(int i = 1; i < s.size(); i++) {	//i为后缀末尾位置，因为后缀不包含首字母，所以从1开始
        /*前后缀不相同的情况：j要向前回退，要看前一位的前缀表的数值，就是要回退的下标，因为要找前面字符串的最长相等前后缀长度*/
        /*j要一直回退，直到前后缀一致，即s[i]==s[j]，此时s[i-1]==s[j-1]、s[i-2]==s[j-2]、......*/
        while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
            j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置。如果一直回退，只能退到next[0]，故上面写j>0。
        }
        /*前后缀相同的情况*/
        if (s[i] == s[j]) { //理解方式1：说明【i之前的子串的最长相等前后缀的长度】加1，即j++
            j++;   			//(更好理解)理解方式2：i之前的缀要与j之前的缀相等(这里的缀等价于上图的aa)，所以j要右移一位，即上图b的位置
        }
        /*更新next数组的值*/
        next[i] = j;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

上述代码的本质：递推，首先知道了next[0]的回退位置0，求next[1]的操作就是：如果前后缀不同则回退，相同则更新next[1]的值；然后再求next[2]，以此类推一步步更新完next数组值。

对上述代码熟悉后，建议看"代码讲解视频"的"模拟运行过程"部分，讲的更加透彻。

利用next数组，从文本串S中找到模式串T的第一个匹配字符的下标（LeetCode28）

思路：参照上面带有红色框和蓝色框的图

int strStr(string S, string T) {
    /*构建前缀表即next数组*/
    int next[T.size()];
    getNext(next, T);
    //指针i遍历文本串S，指针j遍历模式串T
    int j = 0;
    for (int i = 0; i < S.size(); i++) {
        while(j > 0 && S[i] != T[j]) {	//当S[i]!=T[j]时，j要不断回退到下标为【前一个字符的前缀表的数值】的位置，直
            j = next[j - 1];			//到S[i]==T[j]
        }
        if (S[i] == T[j]) {		//若S[i]==T[j]，两个指针同时右移
            j++;
        }
        if (j == T.size() ) {	// 当指针j遍历完模式串T，即在文本串S中找到第一个与模式串T相等的字符串，此时i指向该字符串
            					// 最后一个字符的后一位置
            return (i - T.size() + 1);	//返回该字符串的首字符位置
        }
    }
    return -1;	// 若文本串S中不存在模式串T，则返回-1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

例题：LeetCode28

状态：背完KMP写的。

459

讲解视频：字符串这么玩，可有点难度！ | LeetCode：459.重复的子字符串_哔哩哔哩_bilibili

文章讲解：代码随想录 (programmercarl.com)

状态：不会做。

方法1：移动匹配

思路

对于重复子串组成的字符串，那么其前半部分与后半部分一定相等。eg.ababab的前、后半部分为abab；abcabc的前、后半部分为abc。

对于重复子串组成的字符串s=abcabc，那么s+s=abcabcabcabc，其中间必定存在一个s（加粗部分）。

所以判断s是否由重复子串构成时，只要s+s中间部分(不包含首尾字符)出现了s，那么该字符串s就是由重复子串构成。

代码

bool repeatedSubstringPattern(string s) {
    string t = s + s;
    t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
    if (t.find(s) != std::string::npos) return true; // r
    return false;
}
1
2
3
4
5
6

方法2：KMP

思路

• 定理：若字符串由重复子串组成，那么其最小重复单位就是其最长相等前后缀不包含的那一部分。如下图所示，推导见文档或视频

代码

class Solution {
public:
    //计算next数组。比如next[5]的值表示：字符串s[0--5]的最长相等前后缀的长度。
    //假设字符串s长度为8，那么next[7]就是字符串s的最长相等前后缀的长度。（因为索引从0开始）
    void getNext (int* next, const string& s){	
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++){
            while(j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if(s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern (string s) {
        if (s.size() == 0) {
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        
        int len = s.size();
        //条件1：next[len-1]!=0表示【字符串s的最长相等前后缀长度】不为0，即存在重复子串。只有这个条件可能出现重复子串堆叠的情		//况，如aabaaba的最长相等前后缀长度为4，即aaba，其aab不是最小重复子串。
        //！！条件2：next[len-1]表示字符串s的最长相等前后缀长度，len-next[len-1]表示最小重复子串的长度，
        //！！len%(len-(next[len-1]))==0就是为了杜绝出现“重复子串堆叠”的情况：保证只能是abcabc而不能是aabaaba。
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }
};
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

字符串总结

代码随想录 (programmercarl.com)

双指针总结

代码随想录 (programmercarl.com)