代码随想录算法训练营DAY9|C++字符串Part.2|LeetCode:28.实现strStr()、459.重复的子字符串|KMP算法

28.实现strStr()

力扣题目链接

文章链接：28.实现strStr()

视频链接:

• 帮你把KMP算法学个通透！B站（理论篇）
• 帮你把KMP算法学个通透！（求next数组代码篇）

状态：KMP算法顶中顶，以后一定要搞熟搞透

关于KMP算法的理论基础，这里最推荐的是《大话数据结构》–程杰的讲解。听完卡哥视频之后，再看看这本书关于KMP算法的解释，立马就通透了。

思路

没啥别的，就是KMP算法最基础的应用。

• 构造next函数：定义一个函数getNext来构建next数组，函数参数为指向next数组的指针，和一个字符串。

  void getNext(int* next, const string& s)
  

  • 初始化:定义两个指针i和j。j指向前缀末尾位置，同时j还代表着包括i之前的子串的最长相等前后缀的长度。i指向后缀末尾位置

  int j = 0;	//我们的前缀肯定是从0 开始
  next[0] = j;
  //i的初始化已经进入了循环遍历的过程.在循环中我们需要比较前缀和后缀所对应字符是否相等。所以i必须从1开始
  for (i = 1; i < s.size(); i++){
    
  }
  

  • 处理前后缀不相同的情况:之前我们说过，如果子串遇到不匹配的位置，应该看该位置的前一位，来看这个位置前缀表中对应的值，来回退到前缀表中对应值的数组下标；那么前缀末尾和后缀末尾不匹配的时候,就应该向前回退。其实遇到冲突看前一位就是我们的循环不变量。那么我们的j回退到0位置为止，也就是如果一直前后缀末尾不同，就一直回退到初始位置。

  s[i] != s[j];//前缀末尾和后缀末尾不匹配的时候,就应该向前回退
  j > 0;	//`j`回退到0位置为止，也就是如果一直前后缀末尾不同，就一直回退到初始位置
  
  //综上，处理前后缀不相同的情况代码如下
  while (j > 0; s[i] != s[j]){	//while表示一个连续回退的过程
    j = next[j-1];//回退，看它的前一位的next数组的值。
  }
  
  

  • 处理前后缀相同的情况:还记得之前说过：j指向前缀末尾位置，同时j还代表着包括i之前的子串的最长相等前后缀的长度。所以如果遇到了前后缀相等的情况,j一定要做+1的操作

  if (s[i] == s[j]) j++;
  

  • 更新next数组的值：之前说过，j指向前缀末尾位置，同时j还代表着包括i之前的子串的最长相等前后缀的长度。这里我们直接填入j的值

  //直接填入j的值即可。
  next[i] = j;
  

综上所述，更新完next的值之后，我们还要把i向前走一位，还记得我们是在for循环中遍历的不？

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要保证大于0，因为下面有取j-1作为数组下标的操作
            j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
        }
        if (s[i] == s[j]) {
            j++;
        }
        next[i] = j;
    }
}

• 上述代码的模拟运行过程可以参考：帮你把KMP算法学个通透！（求next数组代码篇）中模拟运行过程部分。

CPP代码

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()];	//定义next数组
        getNext(next, needle);		//初始化next数组
        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和i同时后移
                j++;	//i的增加在for循环里
            }
            if (j == needle.size() ) {									//文本串中出现了模式串
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

459.重复的子字符串

力扣题目链接

文章链接：459.重复的子字符串

视频链接：字符串这么玩，可有点难度！ | LeetCode：459.重复的子字符串

状态：典型的字符串匹配的问题，最主要的难点就是我们如何拿到模式串即字符串的子串呢？

思路

移动匹配

抓到一个重点：任何由重复子串组成的字符串，它的前半部分和后半部分一定是相等的。

其实按照题目的说法，如果这个字符串可以由重复子串构成，那么它前半部分和后半部分肯定是想定的(不过不一定非得从中间劈开的相等)

那么如果这是个重复的字符串，那么我们从后面再重复加一遍，变成s+s，那么这个字符串中也一定是包含了一个新的s，比如s=abcabc,s+s = abc|abcabc|abc,这里就出现了一个新s。但是我们在拼接之后一定要删除首尾字母，以免搜索过程中搜到我们原来的s和后来加的s，如果这样还能找到一个s，那么说明该字符串由重复子串组成。

假设t = s + s;

那么有查找字符串中某个子串或字符位置的方法：

if (t.find(s) != std::string::npos)//如果不等于，意味着find方法成功找到了子串s在字符串t中的位置

在C++中，std::string::npos是一个常量，表示std::string中某个操作（如查找）失败时的返回值。它实际上是std::string类型的最大可能长度，通常被定义为-1。由于std::string的长度是使用无符号整数类型（如size_t）表示的，-1会被转换成无符号类型，结果是这个类型能表示的最大值。

当你使用std::string的find方法或其他可能查找字符串中某个子串或字符位置的方法时，如果查找失败（即未找到指定的子串或字符），方法会返回std::string::npos。因此，通过检查方法的返回值是否等于std::string::npos，你可以判断查找操作是否成功。

KMP算法

这里的KMP算法主要就是用来求最长相等前后缀。因为一个字符串的最长相等前后缀长度就是next[size - 1]。

因为一个由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串。

• 首先让我们复习一下前缀和后缀的概念：

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

• 如何找最小重复子串：

  • 结论：由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串。
  • 证明过程：建议直接去看视频-KMP解法-最小重复子串推导

• 综上，如何进行求解呢？

  • 整个字符串长度len，最长相等前后缀是next[len - 1]
  • 源字符串长度减去最长相等前后缀的长度，剩下的就是最长相等前后缀不包含的子串就是最小重复子串的长度。那么如果是重复子串的话，那么这个长度肯定可以被源字符串长度len整除：

  len % (len - next[size-1]) == 0;
  

CPP代码

移动匹配

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;
    }
};

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();
      //这里next[len-1] ！= 0也就是说该字符串存在最长相等前后缀
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }
};