Day 9 | Leetcode 28, 459, summary

链接

28. 实现 strStr()
459.重复的子字符串
 字符串：总结篇
 双指针总结篇

知识

KMP算法理论

KMP与解决的问题

KMP：发明本算法的三位学者的英文名首字母

应用：字符串匹配问题

经典例子：

给出文本串: aabaabaaf
给出模式串: aabaaf
求在文本串中是否出现过模式串

暴力方法与KMP

暴力解法：两重for循环，先遍历文本串，再遍历模式串，挨个匹配。从文本串的首位开始，若模式串不匹配文本串，则将模式串后移一位，直到匹配上。时间复杂度O(m * n)，m和n分别是文本串和模式串的长度。

KMP算法：跳到之前已匹配的地方，继续匹配。

前缀表的由来

KMP算法如何知道我们之前已匹配过哪些，且跳到已匹配的内容后面继续匹配？

前缀表有什么特性，可以让我们找到之前已匹配过的内容？

在f处不匹配，找到f前面子串的后缀是aa，找到与该后缀相等的前缀的后面开始匹配。故我们要求一个字符串中的最长相等前后缀，重新匹配时跳到最长前缀之后开始匹配。

前缀与后缀

前缀：包含首字母，不包含尾字母的所有子串。

后缀：包含尾字母，不包含首字母的所有子串。

最长相等前后缀

最长相等的前缀和后缀的长度。以模式串aabaaf为例。

子串	前缀	后缀	最长相等的前缀和后缀的长度
a	无	无	0
aa	a	a	1
aab	a, aa	b, ab	0
aaba	a, aa, aab	a, ba, aba	1
aabaa	a, aa, aab, aaba	a, aa, baa, abaa	2
aabaaf	a, aa, aab, aaba, aabaa	f, af, aaf, baaf, abaaf	0

得到模式串的前缀表：010120。

使用前缀表的匹配过程

模式串 aabaaf
前缀表 010120
发现f不匹配，要找f前的最长相等前后缀，由前缀表得到最长相等前后缀为2。2意味着有一个后缀aa，前面也有一个与之相等的前缀aa。在后缀aa的后面不匹配了，就要从与后缀相等的前缀的后面继续开始匹配。最长相等前后缀为2，故从s[2] = 'b'处开始重新匹配。

next数组

next/prefix都可以用来表示前缀表。在遇到不匹配的地方，next数组告诉我们要回退到哪里。前缀表为010120，对其的处理包括：右移/统一减一。不处理前缀表，就将其作为next数组，依然可以完成KMP算法。

总结

KMP算法->能解决哪些问题->为什么KMP算法匹配失败后可以跳到某个位置->前缀表->前缀表的特性及如何求取前缀表->用前缀表完成一次匹配的操作->实现KMP算法时，有时对前缀表统一减一，有时右移，这不设计KMP算法原理性的东西，只是实现上方法不同而已。

KMP算法的代码实现

next数组不同的实现方式

模式串：aabaaf

文本串：aabaabaaf

前缀表：010120，用next数组表示。

如何求next数组？

有人会把前缀表右移，第一位放上-1，得到-101012，作为next数组。
有人会把前缀表整体-1，得到-10-101-1，作为next数组。
有人会直接拿前缀表做Next数组。
上述实现方式都可以，但具体处理逻辑会略有差别。

模式串与文本串在模式串的最后一位f处发生了冲突，看f的前一位的前缀表的值是多少，发现是2，于是跳转到下标为2的位置，即b。如果next数组是前缀表右移得到，就直接比较f对应的next数组的值，发现是2，于是也跳转到b的位置。若next数组是前缀表-1得到，那么就把f的前一位的next数组的值+1，依然跳转到b的位置。

next数组的核心：遇到冲突向前回退。本节我们就拿前缀表作为next数组。

求Next数组的具体代码

共4步：

初始化
处理前后缀不相同的情况
处理前后缀相同的情况
更新next数组的值

// 传入的参数：next数组，我们需要对其进行赋值，模式串s
void getNext(vector<int> next, string s)
{
    // 初始化
    // 指针i：指向后缀末尾位置
    // 指针j：指向前缀末尾位置，还代表着i之前（包括i）的子串的最长相等前后缀的长度
    int j = 0; // 前缀从0开始
    int next[N]; 
    next[0] = 0; // next数组初始位置为0
    
    // 比较前后缀所对应的字符是否相等，故i从1开始，这样i和j才能进行比较
    for (int i = 1; i < s.size(); i ++ )
    {
        // 处理前后缀末尾不相同的情况
        // 因为在一次循环中，i相当于是固定不动的，所以此时j回退
        // j回退到next[j - 1]指向的位置，即遇见冲突，就看next数组（即前缀表）的前一位
        // 不止回退一步，而要连续回退，不能写if，而要写while
        while ( j > 0 && s[i] != s[j]) j = next[j - 1]; // 因为要求j - 1 >= 0，因此要求j > 0
        
        // 处理前后缀相同的情况
        // j代表着i之前（包括i）的子串的最长相等前后缀的长度
        if (s[i] == s[j]) j ++ ;
        
        // 更新next数组，在其中存储i之前（包括i）的子串的最长相等前后缀的长度
        next[i] = j;
    }
}

模拟运行过程

当j指向s[1]，i指向s[2]时，前后缀不匹配，此时next[j - 1] = next[0] = 0，j回退到s[0]，再次比较前后缀是否匹配，发现仍不相同，此时j无法继续回退，我们就更新next数组的值，next[2] = 0，这就代表i = 2之前包括i的子串的最长相等前后缀为0，这与表格中的结果相同。此时i后移一位，指向s[3]，有s[3] == s[0]，j ++，j = 1，next[3] = 1，说明aaba的最长相等前后缀长度是1，这与表格中的结果相同。进入下一轮循环，i = 4，同理。最终用getNext函数完成了对next数组的求值。

总结

用上述函数，求得了next数组，即前缀表。

28. 实现 strStr()

求next数组的代码：

// 传入的参数：next数组，我们需要对其进行赋值，模式串s
void getNext(vector<int> next, string s)
{
    int j = 0; // 前缀从0开始
    int next[N]; 
    next[0] = 0; // next数组初始位置为0
    
    // 比较前后缀所对应的字符是否相等，故i从1开始，这样i和j才能进行比较
    for (int i = 1; i < s.size(); i ++ )
    {
        while ( j > 0 && s[i] != s[j]) j = next[j - 1]; // 因为要求j - 1 >= 0，因此要求j > 0
        
        if (s[i] == s[j]) j ++ ;
        
        // 更新next数组，在其中存储i之前（包括i）的子串的最长相等前后缀的长度
        next[i] = j;
    }
}

用next数组做匹配的代码（文本串s，模式串t）：

int j = 0; // 因为next数组里记录的起始位置为0
for (int i = 0; i < s.size(); i++) { // i从0开始，遍历文本串
    while(j > 0 && s[i] != t[j]) { // 不匹配, j - 1 >= 0 => j > 0
        j = next[j - 1]; // j 寻找之前匹配的位置
    }
    if (s[i] == t[j]) { // 匹配，j和i同时向后移动
        j++; // i的增加在for循环里
    }
    // j指向了模式串t的末尾，那么就说明模式串t完全匹配文本串s里的某个子串了
    if (j == t.size()) { // 文本串s里出现了模式串t
        // 返回当前在文本串匹配模式串的位置i-模式串的长度 + 1，就是文本串字符串中出现模式串的第一个位置（位置从0开始）
        return (i - t.size() + 1);
    }
}

完整代码：

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 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;
        }
    }
    int strStr(string haystack, string needle) {
        // 特殊情况，模式串长度为0，则返回0，本处是一个易错点
        if (needle.size() == 0) {
            return 0;
        }
        // 定义next数组
        int next[needle.size()];
        // 填充next数组
        getNext(next, needle);
        // 用next数组做匹配
        // j指向模式串，i指向文本串
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        // 模式串匹配不上文本串，则返回-1
        return -1;
    }
};

n为文本串长度，m为模式串长度

时间复杂度: 生成next数组，时间复杂度是O(m)；根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)。所以总共的时间复杂度为O(n + m)
空间复杂度: 开辟空间用于存储next数组，即模式串的前缀表，因此是O(m)

459.重复的子字符串

暴力解法

枚举所有的子串，看能否构成字符串。

1 2	for 子串结束位置 for 子串与主串比较

时间复杂度O(n^2)。目标子串的开始位置必然是主串最前面的元素，因此只需要枚举子串的结束位置即可。

移动匹配

设一个可由重复的子串构成的字符串为s，那么两个s拼接起来，前一个s的后半部分和后一个s的前半部分又可以构成一个新的字符串s。s由重复子串构成的判据：两个s相加起来，若其中出现了s，那么s就是由重复子串构成的。

注意：在(s + s)中去搜索s时，一定要把(s + s)的首元素和尾元素删去。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string ss = s + s;
        ss.erase(ss.begin());
        ss.erase(ss.end() - 1);
        
        // string::npos 是 std::string 类型的一个静态成员常量，表示字符串中不存在匹配的位置。在 find() 函数中，如果没有找到匹配的子串，则返回 string::npos。这个值通常是一个很大的无符号整数，表示找不到匹配的位置。
        if (ss.find(s) != string::npos)
            return true;
        else 
            return false;
    }
};

find函数的实现其实就是28. 实现strStr()。若用KMP实现find函数，那么时间复杂度是O(m + n)，find函数的其他实现方法时间复杂度大抵也是O(m + n)。

KMP解法

KMP算法的应用场景：模式串是否在文本串中出现过，即上面的find函数的一种实现方式。

前缀：不包含尾字母，一定包含首字母的所有子串。
后缀：包含尾字母，不包含首字母的所有子串。

结论：若s由重复子串组成，那么它的最小重复单位就是它的最长相等前后缀不包含的那个子串。后缀不包含和前缀不包含的部分是相同的，都是最小重复子串。

举例：abababab，最长相等前缀是ababab，最长相等后缀是ababab，剩余的部分ab即为最小重复子串。

推导：设原字符串是s，标出其下标；设最长相等前缀是t，最长相等后缀是f，也分别标出下标。利用最长相等前缀和最长相等后缀的下标之间的对应关系和最长相等前后缀和原字符串下标之间的对应关系推导即可。

实现：设s存在最小重复单位，len为s的长度，则next[len - 1]为s的最长相等前后缀的长度，最小重复单位的长度为：len - next[len - 1]，若该长度能被原字符串的长度整除：len % (len - next[len - 1]) == 0，那么return true。有如下代码：

class Solution {
public:
    // 求next数组
    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数组
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern (string s) {
        if (s.size() == 0) {
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        // 核心代码
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }
};

初次尝试

28. 实现 strStr()

直接听卡尔讲，尝试去理解，不要求独立写出代码。

459.重复的子字符串

直接听卡尔讲，尝试去理解，不要求独立写出代码。

实现

28. 实现 strStr()

因为KMP算法很难，大家别奢求一次就把kmp全理解了，大家刚学KMP一定会有各种各样的疑问，先留着，别期望立刻啃明白，第一遍了解大概思路，二刷的时候，再看KMP会懂很多。或者说大家可以放弃一刷可以不看KMP，今天来回顾一下之前的算法题目就可以。

因为大家算法能力还没到，细扣很难的算法，会把自己绕进去，就算别人给解释，只会激发出更多的问题和疑惑。所以大家先了解大体过程，知道这么回事，等自己有算法基础和思维了，在看多看几遍视频，慢慢就理解了。

459.重复的子字符串

本题算是KMP算法的一个应用，不过对KMP了解不够熟练的话，理解本题就难很多。

建议是 KMP和本题，一刷的时候，可以适当放过，了解怎么回事就行，二刷的时候再来硬啃

心得与备忘录

28. 实现 strStr()

我觉得KMP算法很想一种特殊的双指针算法。一个指针i用于遍历文本串，另一个指针j用于根据next数组的指引在模式串中移动。这种双指针算法可以把时间复杂度从暴力算法的O(n * m)优化为O(n + m)。
代码分为独立的两部分，第一部分是求next数组（即前缀表），第二部分是同时在两个字符串中移动指针并使用next数组。
当模式串为空时，应当返回0。因为空字符串被认为是任何字符串的子串，所以文本串中最开始与模式串匹配的字符的索引就是0。如果文本串中不存在与之匹配的模式串，则返回 -1。

459.重复的子字符串

本题有两种解法：移动匹配和KMP解法。如果忘记了KMP算法的next数组怎么写，可以使用移动匹配方法（最难写的KMP部分可以用find函数来代劳）。
注意string中find函数的用法：在 find() 函数中，如果没有找到匹配的子串，则返回 string::npos。
本题的KMP解法的关键在于结论：若s由重复子串组成，那么它的最小重复单位就是它的最长相等前后缀不包含的那个子串。

总结

字符串总结

常见题型和常用方法：

花式反转字符串（整体&局部反转，有时还要搭配双指针算法删除空格）
后续处理字符串
KMP算法（匹配模式串和文本串）
移动匹配（核心也是KMP算法，只不过核心由库函数find实现）

小知识：

substr，split，reverse, erase这四个库函数的时间复杂度都是O(n)，在循环中使用会使得程序的时间复杂度达到O(n^2)。此时需要双指针算法等进行优化。
字符串本质为字符数组，数据结构基本等用于普通数组，因此普通数组中常用的双指针算法也常用于字符串中。

双指针总结

双指针应用于：

数组：移除元素
字符串：反转字符串、替换数字、翻转字符串里的单词
链表：反转链表、环形链表II

哈希表章节：三数之和、四数之和，两数之和若要求返回两数的值而非索引，也可以用双指针做，代码如下：

vector<int> twoSum(vector<int> nums, int target)
{
    vector<int> res; // 存储结果
    sort(nums.begin(), nums.end()); // 先排序
    
    int left = 0, right = nums.size() - 1;
    
    while (left < right)
    {
        if (nums[left] + nums[right] > target) right -- ;
        else if (nums[left] + nums[right] < target) left ++ ;
        else
        {
            res.push_back({nums[left], nums[right]}); // 收获答案
            // 去重
            while (left < right && nums[left] == nums[left + 1]) left ++ ;
            while (left < right && nums[right] == nums[right - 1]) right -- ;
            // 寻找新的答案
            left ++ ;
            right -- ;
        }
    }
    return res;
}

上述代码本质上就是三数之和、四数之和的一部分（for循环中的while循环）。相比于两数之和的哈希写法，新增了值去重的功能。

双指针的题目中，以三数、四数之和以及反转链表最容易写错，一定要多复习。三数、四数之和的易错点在于剪枝、去重和求四数之和时的int类型变量的溢出。反转链表的易错点在于搞错了tmp, cur->next, prev和cur更新的先后顺序。