Day9 KMP
By HQWQF 2023/12/21
笔记
28. 实现 strStr()
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
解法：KMP算法
我们将haystack 字符串称为文本串，把要找的needle 字符串称为模式串。如：
在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf
在讲解之前，让我们看这道题的一个错误解法，这种解法可以通过leetcode上大部分测试用例：
错误解法
//错误解法
int strStr(string haystack, string needle) {
int j = 0;
int t = needle.size();
for (int i = 0; c < haystack.size(); i++)
{
//如果碰到needle的首字母就开始比较
if (haystack[i] == needle[j])
{
j++;
}//如果比较中出现了差异就归零
else
{
j = 0;
}
if (j == t)//如果后续比较完了needle都没有差异就说明找到了，返回值
{
return i - j + 1;
}
}
return -1;
}
//运行：h = "theskyisblue" n = "sky" 结果：3
//O(n)
//似乎是正确的解法？
运行发现，这个解法对于"theskyisblue"这样的字符串是正确的，然而这个解法无法通过所有的测试用例，比如：
haystack =
"mississippi"
needle =
"issip"
//正确的答案是4
//错误解法输出-1（没找到）
如果我们观察所有错误解法无法通过的用例，我们会发现其共同特点是：模式串重复包含自身的前缀： issip 中有 i * 2
//mississippi
// issip
//mississippi
// ississip
//iss是模式串issip的前缀
所有像"theskyisblue"这样的、能通过错误解法的字符串都没有这样的性质。在错误解法的过程中，已经匹配到模式串'issip'的一段前缀'iss'但是后续匹配失败后（匹配到'i'而不是'p'），会继续遍历文本串的下一个字符（'s'），考虑这个字符是不是模式串首字符。而这个匹配到的'i'实际上模式串'issip'的开头，是于是文本串中的模式串的开头就被程序跳过了。
错误解法的过程：
尝试比较：
//mississippi
// issip
// x
失败，继续比较：
//mississippi
// issip
// x
继续失败……
所以说，我们不能从比较失败后的下一个位置（文本串中的位置）开始比较，而是回到文本串和模式串开始匹配的下一位继续比较，而这就是这道题的正确解法之一暴力解法：
暴力解法
int strStr(std::string haystack, std::string needle) {
int m = haystack.size();
int n = needle.size();
for (int i = 0; i <= m - n; ++i) {
int j;
for (j = 0; j < n; ++j) {
if (haystack[i + j] != needle[j]) {
break;
}
}
if (j == n) {
return i;
}
}
return -1;
}
//暴力解法的时间复杂度是O(n^2)
接下来，我们介绍更快的KMP算法
回看错误解法的过程：
错误解法的过程：
尝试比较：
//aabaabaafa
//aabaaf
// x
失败，继续比较：
//aabaabaafa
// aabaaf
// x
继续失败……？
在aabaaf这样 重复包含自身的前缀的模式串中
如果我们在比较失败时，尝试在已经匹配成功的部分的后缀中寻找模式串的前缀，从这个前缀开始继续匹配模式串：
尝试比较：
//aabaabaafa
//aabaaf
// x
作偏移，比较：
// i
//ooooo //匹配成功的部分
// ** //模式串的前缀，匹配成功的部分的后缀
//aabaabaafa
// aabaaf
//成功
我们就能避免错误解法中的遗漏，将错误解法变得正确
这样的做法对应到修正后的代码中，就是把模式串中的下标j偏移到一个新的位置，新的位置在数值上等于=我们在匹配成功的部分、的后缀、找到的模式串的前缀、的长度
//修正后的错误解法的伪代码
int strStr(string haystack, string needle) {
int j = 0;
int t = needle.size();
for (int i = 0; i < haystack.size(); i++)
{
//如果碰到needle的首字母就开始比较
if (haystack[i] == needle[j])
{
j++;
}//如果比较中出现了差异就归零
else
{
// i
//ooooo //匹配成功的部分
// ** //模式串的前缀
//aabaabaafa
//aabaaf
// j //old
// j //new
j = 新的位置();
}
if (j == t)//如果后续比较完了needle都没有差异就说明找到了，返回值
{
return i - j + 1;
}
}
return -1;
}
那么我们应该如何在匹配成功的部分找到模式串的前缀，并获取其长度，实现新的位置() 这个函数呢？
注意这样一个事实，匹配成功的部分实际上就是模式串的一部分，所以我们可以到模式串的一部分（也就是模式串的子串）的后缀中寻找寻找模式串的前缀
后缀：不包括第一个字符的连续子串
前缀：不包括最后一个字符的连续子串
为了描述我们要找的这串前后缀的长度，我们引入【最长相等前后缀】的概念：
//以aabaaf的一系列子串为例
aabaaf的最长相等前后缀：a != f 为0
aabaa的最长相等前后缀：aa == aa 为2
aaba的最长相等前后缀：a == a 为1
aab的最长相等前后缀：a != b 为0
aa的最长相等前后缀：a == a 为1
a的最长相等前后缀：没有前后缀 为0
匹配成功的部分实际上就是这样的模式串的子串，即头字符固定，尾字符不定。
我们可以将模式串一系列子串的【最长相等前后缀】和字串的尾字符作一个映射，获得一个前缀表，将其实现为一个数组next[]，数组的下标对应模式串中的下标，值对应模式串中以该下标的字符结尾，以头字符开始的字串的【最长相等前后缀】。
//模式串 aabaaf
//前缀表 010120
这样我们就可以通过next[j]获取新的位置了。接下来我们将其实现为代码
制作前缀表的代码？
void getNext(int* next, const string& s) {
int n = s.size();
for (int i = 0; i < n; i++) {
next[i] = 0;
for (int j = 1; j <= i; j++) {
if (s.substr(0, j) == s.substr(i - j + 1, j)) {
next[i] = j;
}
}
}
}
不难发现，这个制作前缀表的函数的时间复杂度是O(n2)，而暴力解法的时间复杂度也是O(n2)，并没有提升，所以我们需要更加快的getNext函数。
更加快的getNext函数
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;
}
}
解析
我们注意到：
//子串 aaba 最长相等前后缀：1
//子串 aabaa 最长相等前后缀：2
//递进的子串之间的最长相等前后缀有某种递进的关系，利用这种递进实现线性的时间复杂度
使用一个循环遍历从a到 aabaaf的子串。
我们定义一个指向前缀尾的下标j，指向后缀尾的下标i（也是当前子串尾），在遍历到下一个字串时，将j和i递增，如果s[i] == s[j]，意味着这个字串的最长相等前后缀是上一个字串的最长相等前后缀+1
//对于子串 aaba 来说j为0，i为3 最长相等前后缀：1
//对于子串 aabaa 来说j为1，i为4 最长相等前后缀：2
如果新的i和j出现s[i] ！= s[j]的情况了呢？
这意味着对于这个新的子串来说，从串头到j的这部分前缀找不到相等的后缀，因此我们需要把前缀尾j左移。
然而如何只是j = j - 1，当s[i] == s[j]，我们并不能确认j左边的字符等于i左边的字符，需要更多的逻辑来确认。
我们可以利用已经构成的前缀表next[]，让j一直j = next[j - 1]，直到s[i] == s[j]或者j = 0。
为什么next[j - 1]能为我们节省计算？
//以cdcadcd为例
过程1.
//cdcadcd
// j i //s[i] == s[j]
过程2.j++,i+++
//cdcadcd
// j i //s[i] != s[j]
//此时我们知道，j左边的字符一定等于i左边的字符，因为我们经历了过程1
//此时next[j - 1]代表子串cdc的最长相等前后缀的长度，数值上等于子串前缀尾（如果有）的下一个字符的下标
//如果假设存在一个j的位置指向一个合适的前缀尾，上面的字符是’d‘，这个字符’d‘的左边是字符’c‘，
//那么这个位置一定等于子串cdc的最长相等前后缀的长度，
//因为过程2j左边的字符一定等于i左边的字符，而如果j的新位置左边的字符要为当前j左边的字符’c‘，这个位置只能是
//子串cdc前缀尾（如果有）的下一个字符
//也就是下标为next[j - 1]的位置
//其他情况以此类推
完整代码
//O(n)
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) {
if (needle.size() == 0) {
return 0;
}
int next[needle.size()];
getNext(next, needle);
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);
}
}
return -1;
}
};
459.重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
- 输入: "abab"
- 输出: True
- 解释: 可由子字符串 "ab" 重复两次构成。
解法：移动匹配 和 KMP两种方法。
移动匹配：当一个字符串s：abcabc，内部由重复的子串组成，那么如果创建一个新字符串s+s：abcabcabcabc
其中一定还能组成一个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;
}
};
当然这里出现了find()这个库函数，如果不用的话要用KMP解决：
KMP代码
class Solution {
public:
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();
if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
return true;
}
return false;
}
};
待续