代码随想录算法训练营第九天 | 28. 实现 strStr()，459.重复的子字符串，字符串总结，双指针回顾

一、参考资料

实现 strStr()

题目链接/文章讲解/视频讲解：https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html

重复的子字符串

题目链接/文章讲解/视频讲解：https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html

字符串总结

题目链接/文章讲解：https://programmercarl.com/%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%80%BB%E7%BB%93.html

双指针回顾

文章讲解：https://programmercarl.com/%E5%8F%8C%E6%8C%87%E9%92%88%E6%80%BB%E7%BB%93.html

二、LeetCode28. 实现 strStr()

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
提示：
1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

KMP，前缀表统一减一

class Solution {
public:
    // 前缀表统一减一 C++代码实现
    void getNext(int *next, const string &s) {
        // 初始化
        int j = -1;
        next[0] = j;
        // 注意i从1开始的
        for (int i = 1; i < s.size(); i++) {
            // 前后缀不相同的情况，用while回退
            while (j >= 0 && s[i] != s[j + 1]) {
                j = next[j];   // 向前回退
            }
            // 前后缀相同的情况
            if (s[i] == s[j + 1]) {
                j++;
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        // 因为next数组里记录的起始位置为-1
        int j = -1;
        // i从0开始
        for (int i = 0; i < haystack.size(); i++) {
            while(j >= 0 && haystack[i] != needle[j + 1]) {
                j = next[j];
            }
            // 匹配，i和j同时向后移动
            if(haystack[i] == needle[j + 1]) {
                j++;
            }
            // 文本串s中出现了模式串t
            if(j == (needle.size() - 1)) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

KMP，前缀表不减一

class Solution {
public:
    // 前缀表不减一 C++代码实现
    void getNext(int *next, const string &s) {
        // 初始化
        int j = 0;
        next[0] = 0;
        // 注意i从1开始的
        for (int i = 1; i < s.size(); i++) {
            // 前后缀不相同的情况，用while回退
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];   // 向前回退
            }
            // 前后缀相同的情况
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        // 因为next数组里记录的起始位置为-1
        int j = 0;
        // i从0开始
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            // 匹配，i和j同时向后移动
            if(haystack[i] == needle[j]) {
                j++;
            }
            // 文本串s中出现了模式串t
            if(j == needle.size()) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

我个人更倾向于不减一的代码理解

三、LeetCode459.重复的子字符串

https://leetcode.cn/problems/repeated-substring-pattern/

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:
输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba" 输出: false
示例 3:
输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
提示：
1 <= s.length <= 104
s 由小写英文字母组成

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

u1s1，这题我还没理解到位

总结：

1. KMP的原理看完资料能理解原理，就是代码实现还需要进一步实践；

2. 总的来说KMP分为三步：初始化、求前缀表（包括前后缀相同和前后缀不同时两种情况）、通过next数组匹配；

3. 而next数组有三种常见情况：① 就用前缀表；② 前缀表元素统一减一；③ 前缀表元素统一右移一位，next[0] = -1。在这三种情况中，前两个的理解是完全一样的，当冲突发生时，匹配的是当前冲突前一元素对应的next数组的值，如果选了①，next数组的值表示的恰好是回退到的数组（这个数组指模式串）下标，如果选了②，next数组的值＋1表示回退到的模式串下标。

刷题加油鸭~~