KMP算法

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

构造前缀表

解决字符串匹配的问题

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

当字符不匹配时，就要跳到最长相等的前缀 的后面

构造next数组

​ 1.初始化前缀表： j为前缀末尾位置 i为后缀末尾位置

j = 0;next[j] = j ;而i的初始化为for(int i = 1 ; i < s.length() ; i++ )，如果s[i] 和 s[j+1]不同，就要找j+1前一个元素在next数组里的值。（就是next[j]）

​ 2.前后缀不相同：j要回退回去， if ( j > 0 && s[i] != s[j+1] ) j = next[j]

​ 3.前后缀相同：需要同时向后移动 i 和 j ，还需要将j （前缀的长度）赋给next[i]，因为next[i] 要记录相同前后缀的长度，if (s[i] == s[j+1])j++; next[i]=j

使用next数组来做匹配

重复上述的操作。但是其实并不理解为什么要这样做。

28.实现strStr()

文章：6. 实现strStr())

题目：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

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

  • Java实现
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
class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0)return 0;
        int[]next = new int[needle.length()];
        getNext(next,needle);
        int j=0;
        for(int i = 0 ; i < haystack.length();i++){
            while(j > 0 && haystack.charAt(i) != needle.charAt(j)){
                j = next[j-1];
            }
            if(haystack.charAt(i) == needle.charAt(j)){
                j++;
            }
            if(j == needle.length()){
                return i - needle.length()+1;
            }
        }
        return -1;

    }
    public void getNext(int[]next ,String s){
        int j = 0 ;
        next[0] = j;
        for(int i = 1 ; i < s.length();i++){
            //字符串不匹配：
            while(j > 0 && s.charAt(j) != s.charAt(i)){
                j = next[j-1];
            }
            //字符串匹配： 
           if(s.charAt(i) == s.charAt(j)){
               j++;
           }
            //更新next数组
            next[i] = j;
        }
            

    }

    
}
  • Go实现
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
func strStr(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }
    next := make([]int,len(needle))
    j :=0
    getNext(needle,next)
    h := []byte(haystack)
    n := []byte(needle)

    for i :=0;i<len(haystack);i++{
        for j > 0 && h[i]!= n[j]{
            j = next[j-1]
        }
        if h[i] == n[j]{
            j++
        }
        if j == len(needle){
            return i - len(needle)+1
        }
    }
    return -1
}
func getNext(s string ,next[]int)[]int{
    b := []byte(s)
    j := 0
    next[0] = j
    for i:=1 ; i <len(s);i++{
        for j >0 && b[i] != b[j]{
            j = next[j-1]
        }
        if b[i] == b[j]{
            j++
        }
        next[i] = j
    }
    return next
}

459.重复的子字符串（跳过）

状态不太好，，有机会补

字符串总结篇

什么是字符串

字符串是若干字符组成的有限序列，也可以理解为是一个字符数组，但是很多语言对字符串做了特殊的规定。

要不要使用库函数

强调了打基础的时候，不要太迷恋于库函数。

如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。

如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。

双指针法

在344.反转字符串 (opens new window)，我们使用双指针法实现了反转字符串的操作，双指针法在数组，链表和字符串中很常用。

接着在字符串：替换空格 (opens new window)，同样还是使用双指针法在时间复杂度O(n)的情况下完成替换空格。

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

那么针对数组删除操作的问题，其实在27. 移除元素 (opens new window)中就已经提到了使用双指针法进行移除操作。

同样的道理在151.翻转字符串里的单词 (opens new window)中我们使用O(n)的时间复杂度，完成了删除冗余空格。

一些同学会使用for循环里调用库函数erase来移除元素，这其实是O(n^2)的操作，因为erase就是O(n)的操作，所以这也是典型的不知道库函数的时间复杂度，上来就用的案例了。

反转系列

541. 反转字符串II (opens new window)中，一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。

其实当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

因为要找的也就是每2 * k 区间的起点，这样写程序会高效很多。

在151.翻转字符串里的单词 (opens new window)中要求翻转字符串里的单词，这道题目可以说是综合考察了字符串的多种操作。是考察字符串的好题。

这道题目通过 先整体反转再局部反转，实现了反转字符串里的单词。

后来发现反转字符串还有一个牛逼的用处，就是达到左旋的效果。

在字符串：反转个字符串还有这个用处？ (opens new window)中，我们通过先局部反转再整体反转达到了左旋的效果。

KMP

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

KMP的精髓所在就是前缀表，在KMP精讲 (opens new window)中提到了，什么是KMP，什么是前缀表，以及为什么要用前缀表。

前缀表：起始位置到下标i之前（包括i）的子串中，有多大长度的相同前缀后缀。

那么使用KMP可以解决两类经典问题：

  1. 匹配问题：28. 实现 strStr()(opens new window)
  2. 重复子串问题：459.重复的子字符串(opens new window)

再一次强调了什么是前缀，什么是后缀，什么又是最长相等前后缀。

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

后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串。

然后针对前缀表到底要不要减一，这其实是不同KMP实现的方式，我们在KMP精讲 (opens new window)中针对之前两个问题，分别给出了两个不同版本的的KMP实现。

其中主要理解j=next[x]这一步最为关键！

总结

字符串类类型的题目，往往想法比较简单，但是实现起来并不容易，复杂的字符串题目非常考验对代码的掌控能力。

双指针法是字符串处理的常客。

KMP算法是字符串查找最重要的算法。

双指针总结篇

数组篇

在数组：就移除个元素很难么？ (opens new window)中，原地移除数组上的元素，我们说到了数组上的元素，不能真正的删除，只能覆盖。

此时使用双指针法才展现出效率的优势：通过两个指针在一个for循环下完成两个for循环的工作。

字符串篇

在字符串：这道题目，使用库函数一行代码搞定 (opens new window)中讲解了反转字符串，注意这里强调要原地反转，要不然就失去了题目的意义。

使用双指针法，定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。，时间复杂度是O(n)。

在替换空格 (opens new window)中介绍使用双指针填充字符串的方法，如果想把这道题目做到极致，就不要只用额外的辅助空间了！

思路就是首先扩充数组到每个空格替换成”%20”之后的大小。然后双指针从后向前替换空格。

有同学问了，为什么要从后向前填充，从前向后填充不行么？

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。

其实很多数组（字符串）填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

那么在字符串：花式反转还不够！ (opens new window)中，我们使用双指针法，用O(n)的时间复杂度完成字符串删除类的操作，因为题目要删除冗余空格。

在删除冗余空格的过程中，如果不注意代码效率，很容易写成了O(n^2)的时间复杂度。其实使用双指针法O(n)就可以搞定。

链表篇

翻转链表是现场面试，白纸写代码的好题，考察了候选者对链表以及指针的熟悉程度，而且代码也不长，适合在白纸上写。

在链表：听说过两天反转链表又写不出来了？ (opens new window)中，讲如何使用双指针法来翻转链表，只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。

思路还是很简单的，代码也不长，但是想在白纸上一次性写出bugfree的代码，并不是容易的事情。

在链表中求环，应该是双指针在链表里最经典的应用，在链表：环找到了，那入口呢？ (opens new window)中讲解了如何通过双指针判断是否有环，而且还要找到环的入口。

使用快慢指针（双指针法），分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

N数之和篇

在哈希表：解决了两数之和，那么能解决三数之和么？ (opens new window)中，讲到使用哈希法可以解决1.两数之和的问题

其实使用双指针也可以解决1.两数之和的问题，只不过1.两数之和求的是两个元素的下标，没法用双指针，如果改成求具体两个元素的数值就可以了，大家可以尝试用双指针做一个leetcode上两数之和的题目，就可以体会到我说的意思了。

使用了哈希法解决了两数之和，但是哈希法并不使用于三数之和！

使用哈希法的过程中要把符合条件的三元组放进vector中，然后在去去重，这样是非常费时的，很容易超时，也是三数之和通过率如此之低的根源所在。

去重的过程不好处理，有很多小细节，如果在面试中很难想到位。

时间复杂度可以做到O(n^2)，但还是比较费时的，因为不好做剪枝操作。

所以这道题目使用双指针法才是最为合适的，用双指针做这道题目才能就能真正体会到，通过前后两个指针不算向中间逼近，在一个for循环下完成两个for循环的工作。

只用双指针法时间复杂度为O(n^2)，但比哈希法的O(n^2)效率高得多，哈希法在使用两层for循环的时候，能做的剪枝操作很有限。

在双指针法：一样的道理，能解决四数之和 (opens new window)中，讲到了四数之和，其实思路是一样的，在三数之和的基础上再套一层for循环，依然是使用双指针法。

对于三数之和使用双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。

同样的道理，五数之和，n数之和都是在这个基础上累加。

#总结

本文中一共介绍了leetcode上九道使用双指针解决问题的经典题目，除了链表一些题目一定要使用双指针，其他题目都是使用双指针来提高效率，一般是将O(n^2)的时间复杂度，降为O(n)。