JackCin's blog
JackCin
2023-09-13
目录

KMP算法

# 实现strStr()

力扣题目链接(opens new window) (opens new window)

# 一、题目

  • 实现 strStr() 函数。
  • 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2

示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
1
2
3
  • 说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

# 二、思路

本题是KMP 经典题目。

KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

本篇将以如下顺序来讲解KMP，

  • 什么是KMP
  • KMP有什么用
  • 什么是前缀表
  • 为什么一定要用前缀表
  • 如何计算前缀表
  • 前缀表与next数组
  • 使用next数组来匹配
  • 时间复杂度分析
  • 构造next数组
  • 使用next数组来做匹配
  • 前缀表统一减一 C++代码实现
  • 前缀表（不减一）C++实现
  • 总结

# 1、什么是KMP

  • KMP这个名字是怎么来的，为什么叫做KMP呢。
  • 因为是由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP

# 2、KMP的作用

  • KMP主要应用在字符串匹配上。

  • KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

  • 所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

  • next数组里的数字表示的是什么，为什么这么表示？

# 3、前缀表

  • 写过KMP的同学，一定都写过next数组，那么这个next数组究竟是个啥呢？
  • next数组就是一个前缀表（prefix table）。
  • 前缀表有什么作用呢？
    • 前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

为了清楚地了解前缀表的来历，我们来举一个例子：

要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。

如动画所示：

KMP详解1

  • 动画里，我特意把 子串aa 标记上了，这是有原因的，大家先注意一下，后面还会说到。

  • 可以看出，文本串中第六个字符b 和 模式串的第六个字符f，不匹配了。如果暴力匹配，发现不匹配，此时就要从头匹配了。

  • 但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配。

  • 此时就要问了前缀表是如何记录的呢？

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

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

# 4、最长公共前后缀

  • 文章中字符串的

    • 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
    • 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

  • 正确理解什么是前缀什么是后缀很重要!

那么网上清一色都说 “kmp 最长公共前后缀” 又是什么回事呢？

我查了一遍 算法导论 和 算法4里KMP的章节，都没有提到 “最长公共前后缀”这个词，也不知道从哪里来了，我理解是用“最长相等前后缀” 更准确一些。

  • 因为前缀表要求的就是相同前后缀的长度。

例如上面动画里的 aabaafa 我们可以看出它各个子串的最长公共/相等前后缀 。

  • 而最长公共前后缀里面的“公共”，更像是说前缀和后缀公共的长度。这其实并不是前缀表所需要的。

  • 所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等.....。

a       ---->  0
aa      ---->  1    //前缀：a   后缀：a
aab     ---->  0   	//前缀：a，aa   后缀： b，ab  最长相等为1
aaba    ---->  1	//前缀 ：a，aa，aab   后缀：a，ba，aba  无最长相等
aabaa   ---->  2    //前缀：a，aa，aab，aaba  后缀：a，aa，baa，abaa  最长相等为2
aabaaf  ---->  0	//前：a，aa，aab，aaba，aabaa  后：f，af，aaf，baaf，abaaf 无最长相等
1
2
3
4
5
6

# 5、为什么使用前缀表

这就是前缀表，那为啥就能告诉我们 上次匹配的位置，并跳过去呢？

回顾一下，刚刚匹配的过程在下标5的地方遇到不匹配，模式串是指向f，如图： KMP精讲1

然后就找到了下标2，指向b，继续匹配：如图： KMP精讲2

以下这句话，对于理解为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配 非常重要！

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

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

很多介绍KMP的文章或者视频并没有把为什么要用前缀表？这个问题说清楚，而是直接默认使用前缀表。

个人理解：按上面这个，如果指向模式串的指针能指向5，那么说明字符串内有一段前面都匹配成功的字符串，这时如果下标5位置不匹配，那么因为前面那段字符串 aabaa 最大相等子串为aa，所以字符串 对应第5位的前两位仍然会和模式串的前两位匹配，所以我们把模式串下标给到模式串最长相等前缀之后继续进行匹配判断操作

KMP精讲2

# 6、获取前缀表（next）

构造next数组其实就是计算模式串s，前缀表的过程。 主要有如下三步：

  1. 初始化
  2. 处理前后缀不相同的情况
  3. 处理前后缀相同的情况

# 6.1 不做处理写法

void getNext(int * next,char* s){
    //初始化next[0]和 j 
    int j =0 ;
    next[0] = j;
    //i = 1,第零位不用判断，必定为 0 ，所以我们判断从 第一位开始
    for(int i = 1; i< strlen(s); i++){
        //无相等前后缀（进行回退）,要回退那j指向必须大于第0位才可以，如果指向第0位，就不用,所以判断必须j>0
        while(j > 0 && s[i] != s[j]) {
            //回退到判断不同时，j回退到j在next中对应的前一位的的位置
            j = next[j-1];  
        }
        //处理相同前后缀
        if(s[j] ==s[i]){
            j++;
        }
        next[i] = j;   // 将j（前缀的长度）赋给next[i]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 6.2 统一减一写法

void getNext(int * next,char* s){
    //初始化，j和next ，统一减一写法
    int j=-1;
    next[0]= j;
    for(int i =1;i<strlen(s);i++){
        //因为我们j初始化 -1，所以这里判断条件 j可以等于0，判断时j也要先加1来判断
       while( j>=0 && s[i] !=  s[j+1]){
           j = next[j];  //跳到对应位置的前一位，但是我们这里初始j=-1，就相当于已经给往前移了一位了，所以这里是next[j]而不是next[j-1]
       }
       if(s[i] == s[j+1]){
           j++; //相等说明有相等前缀，j++记录相等前缀个数
       }
       next[i] = j;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 三、代码

# 1、统一减一

  • 这个构建next数组的函数，可以用 aabaaa 和 aabaaf 带入尝试，能更好理解
void getNext(int* next,char* s){
    int len = strlen(s);
    //初始化j和next
    //初始化j为-1，就是统一减一的写法
    int j =-1;
    next[0] =j;

    //j指向前缀末尾位置，i指向后缀末尾位置
    for(int i=1 ; i<len ; i++ ){
        // 判断前后缀不同
        while( j >= 0 && s[i] != s[j+1]){
            j= next[j];
        }
        //判断前后缀相同
        if(s[i] == s[j+1]){
            j++;
        }
        //next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度。
        next[i] = j;
    }
}

int strStr(char * haystack, char * needle){
    if(strlen(needle) == 0){
        return 0;
    }
    int next[strlen(needle)];
    getNext(next,needle);
    int j = -1; //因为next数组里记录的起始位置为-1
    for(int i = 0; i < strlen(haystack); i++ ){

        //不匹配就回退
        while(j>=0 && haystack[i] != needle[j+1]){
            j = next[j];  //j 寻找之前匹配的位置
        }
        if(haystack[i] == needle[j+1]){
            j++;
        }
        // j 等于模式串长度 说明匹配成功
        if(j== (strlen(needle) - 1)){
            //获取第一个匹配项的下标
            return (i - strlen(needle) +1);
        }
    }
    return -1;

}
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

# 2、不减1写法

void getNext(int* next,char* s){
    int len = strlen(s);
    //初始化j和next
    //初始化j为-1，就是统一减一的写法
    int j =0;
    next[0] =j;

    //j指向前缀末尾位置，i指向后缀末尾位置
    for(int i=1 ; i<len ; i++ ){
        // 判断前后缀不同
        while( j > 0 && s[i] != s[j]){
            j= next[j-1];
        }
        //判断前后缀相同
        if(s[i] == s[j]){
            j++;
        }
        //next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度。
        next[i] = j;
    }
}

int strStr(char * haystack, char * needle){
    if(strlen(needle) == 0){
        return 0;
    }
    int next[strlen(needle)];
    getNext(next,needle);
    int j = 0; //因为next数组里记录的起始位置为0
    for(int i = 0; i < strlen(haystack); i++ ){

        //不匹配就回退
        while(j > 0 && haystack[i] != needle[j]){
            j = next[j-1];  //j 寻找之前匹配的位置
        }
        if(haystack[i] == needle[j]){
            j++;
        }
        // j 等于模式串长度 说明匹配成功
        if(j== strlen(needle)){
            //获取第一个匹配项的下标
            return (i - strlen(needle) +1);
        }
    }
    return -1;

}
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

# 四、时间复杂度分析

  • 其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是**O(n+m)**的。
  • 暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大地提高了搜索的效率。

其他具体的细节请看：[代码随想录 (programmercarl.com) (opens new window)](https://www.programmercarl.com/0028.实现strStr.html#其他语言版本)

# 重复的子字符串

459. 重复的子字符串 - 力扣（LeetCode） (opens new window)

# 一、题目

  • 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。

示例 2:
输入: "aba"
输出: False

示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
1
2
3
4
5
6
7
8
9
10
11
12
13

# 二、思路

# 1、暴力解法

  • 暴力的解法， 就是一个for循环获取子串的终止位置， 然后判断子串是否能重复构成字符串，又嵌套一个for循环，所以是O(n^2)的时间复杂度。
  • 有的同学可以想，怎么一个for循环就可以获取子串吗？ 至少得一个for获取子串起始位置，一个for获取子串结束位置吧。
  • 其实我们只需要判断，以第一个字母为开始的子串就可以，所以一个for循环获取子串的终止位置就行了。 而且遍历的时候 都不用遍历结束，只需要遍历到中间位置，因为子串结束位置大于中间位置的话，一定不能重复组成字符串。

# 2、移动匹配

  • 当一个字符串s：abcabc，内部由重复的子串组成，那么这个字符串的结构一定是这样的：

图一

  • 也就是由前后相同的子串组成。

  • 那么既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前后的子串做后串，就一定还能组成一个s，如图：

图二

  • 所以判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。

  • 当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。

代码如下：

class Solution {
public:
    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
7
8
9

不过这种解法还有一个问题，就是 我们最终还是要判断 一个字符串（s + s）是否出现过 s 的过程，大家可能直接用contains，find 之类的库函数。 却忽略了实现这些函数的时间复杂度（暴力解法是m * n，一般库函数实现为 O(m + n)）。

如果我们做过 28.实现strStr (opens new window) (opens new window)题目的话，其实就知道，实现一个 高效的算法来判断 一个字符串中是否出现另一个字符串是很复杂的，这里就涉及到了KMP算法。

# 3、KMP算法

  • 在一个串中查找是否出现过另一个串，这是KMP的看家本领。
  • 在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串，这里拿字符串s：abababab 来举例，ab就是最小重复单位，如图所示：
  • 图三

# 最小重复子串

图四

  • 步骤一：因为 这是相等的前缀和后缀，t[0] 与 k[0]相同， t[1] 与 k[1]相同，所以 s[0] 一定和 s[2]相同，s[1] 一定和 s[3]相同，即：，s[0]s[1]与s[2]s[3]相同 。
  • 步骤二： 因为在同一个字符串位置，所以 t[2] 与 k[0]相同，t[3] 与 k[1]相同。
  • 步骤三： 因为 这是相等的前缀和后缀，t[2] 与 k[2]相同 ，t[3]与k[3] 相同，所以，s[2]一定和s[4]相同，s[3]一定和s[5]相同，即：s[2]s[3] 与 s[4]s[5]相同。
  • 步骤四：循环往复。
  • 所以字符串s，s[0]s[1]与s[2]s[3]相同， s[2]s[3] 与 s[4]s[5]相同，s[4]s[5] 与 s[6]s[7] 相同。
  • 正是因为 最长相等前后缀的规则，当一个字符串由重复子串组成的，最长相等前后缀不包含的子串就是最小重复子串。

# 4、计算推理：

  • 假设字符串s使用多个重复子串构成（这个子串是最小重复单位），重复出现的子字符串长度是x，所以s是由n * x组成。

  • 因为字符串s的最长相同前后缀的长度一定是不包含s本身，所以 最长相同前后缀长度必然是m * x，而且 n - m = 1，（这里如果不懂，看上面的推理）

  • 所以如果 nx % (n - m)x = 0，就可以判定有重复出现的子字符串。

  • next 数组记录的就是最长相同前后缀 字符串：KMP算法精讲 (opens new window) (opens new window)这里介绍了什么是前缀，什么是后缀，什么又是最长相同前后缀)， 如果 next[len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。

  • 最长相等前后缀的长度为：next[len - 1] + 1。(这里的next数组是以统一减一的方式计算的，因此需要+1，两种计算next数组的具体区别看这里：字符串：KMP算法精讲 (opens new window) (opens new window))

  • 数组长度为：len。

  • 如果len % (len - (next[len - 1] + 1)) == 0 ，则说明数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除 ，说明该字符串有重复的子字符串。

  • 数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

  • 强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法

如图：

459.重复的子字符串_1

  • next[len - 1] = 7，next[len - 1] + 1 = 8，8就是此时字符串asdfasdfasdf的最长相同前后缀的长度。

  • (len - (next[len - 1] + 1)) 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以被 12(字符串的长度) 整除，所以说明有重复的子字符串（asdf）。

# 三、代码

# 1、不做减一处理

//不对next进行统一减一写法
void getNext(int * next,char* s){
    //初始化next[0]和 j 
    int j =0 ;
    next[0] = j;
    //i = 1,第零位不用判断，必定为 0 ，所以我们判断从 第一位开始
    for(int i = 1; i< strlen(s); i++){
        //无相等前后缀（进行回退）,要回退那j必需指向第1位才可以，如果指向第0位，就不用,所以判断必须j>0
        while(j > 0 && s[i] != s[j]) {
            //回退到判断不同时，j回退到j在next中对应的前一位的的位置
            j = next[j-1];  
        }
        if(s[j] ==s[i]){
            j++;
        }
        next[i] = j;
    }
}

bool repeatedSubstringPattern(char * s){
    int len = strlen(s);
    if(len == 0 ){
        return false;
    }
    int next[len];
    getNext(next,s);
     //不等于-1，说明有最长相同前后缀
    //后面的判断看代码随想录
    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
35

# 2、统一减一

void getNext(int * next,char* s){
    //初始化，j和next ，统一减一写法
    int j=-1;
    next[0]= j;
    for(int i =1;i<strlen(s);i++){
       while( j>=0 && s[i] !=  s[j+1]){
           j = next[j];  //跳到对应位置的前一位，但是我们这里初始j=-1，就相当于已经给往前移了一位了，所以这里是next[j]而不是next[j-1]
       }
       if(s[i] == s[j+1]){
           j++; //相等说明有相等前缀，j++记录相等前缀个数
       }
       next[i] = j;
    }
}

bool repeatedSubstringPattern(char * s){
    int len = strlen(s);
    if(len ==0 ){
        return false;
    }
    int next[len];  //初始化next数组
    getNext(next,s);
    //不等于-1，说明有最长相同前后缀
    //后面的判断看代码随想录
    if(next[len -1] != -1  && len % (len - (next[len -1] +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
编辑 (opens new window)
上次更新: 2023/09/13, 12:29:52
动态规划

←

最近更新
01
51单片机及补充知识
09-13
02
独立按键
09-13
03
LCD1602液晶显示器
09-13
更多文章>
Theme by Vdoing | Copyright © 2019-2023 Evan Xu | MIT License