算法刷题Day9 | 28. 实现 strStr()、459.重复的子字符串、字符串总结

• 🙋‍♂️ 作者：海码007
• 📜 专栏：算法专栏
• 💥 标题：算法刷题Day8 | 28. 实现 strStr()、459.重复的子字符串、字符串总结
• ❣️ 寄语：书到用时方恨少，事非经过不知难！

0 引言

1 实现 strStr()

• 🎈 文档讲解：https://programmercarl.***/0028.%E5%AE%9E%E7%8E%B0strStr.html
• 🎈 视频讲解：最浅显易懂的 KMP 算法讲解
• 🎈 做题状态：KMP算法的next数组的求解还是有点懵

1.1 我的解题

暴力解题：直接两个循环

class Solution {
public:
    int strStr(string haystack, string needle) {
        for(int i = 0; i < haystack.size(); i++)
        {
            int j = 0;
            for (; j < needle.size(); j++)
            {
                if (haystack[i+j] != needle[j])
                {
                    // 如果第一个数都不匹配，则直接跳出循环
                    break;
                }
            }
            // 如果全部的数都匹配，则此时 j == needle.size()
            if (j == needle.size())
            {
                return i;
            }
        }

        return -1;
    }
};

1.2 KMP算法解题

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

如上图所示，只需要我们找到已经匹配过的字符串中前缀和后缀相等的个数，就知道下一次遍历，子串应该从哪个位置开始。例如下图中，在C处不匹配时，我们只需要找出 ABAB 这个字符串，最小的前后串相等的个数是多少，就知道下次遍历子串该从哪个位置开始。 对于 ABAB 字符串，可以得知最小前后串相等的个数是2。所以子串从 （2+1）的位置开始遍历，也就是从 索引为 2 的位置开始遍历。因为主串中末尾匹配的字符对应 ABAB 的后缀。而我们已经知道 ABAB 的 AB前缀和AB后缀是相等的。所以此时 AB 前缀也就不需要再和主串中末尾的 AB 进行比较了。

现在知道匹配的基本原理后，下一步的任务就是求解 前缀表 也就是子串中当前字符前面的字符串的相同前后缀的长度是多少。也就是next数组。

使用递推求解next数组：

next数组（前缀表）求解的步骤：
初始化、前后缀不相同的情况、前后缀相同的情况、更新next数组

1. 初始化，两个索引值，分别指向前缀末尾（索引 j ）和后缀末尾（索引 i ）。首先初始化 j=0; next[0] = 0;
2. 遍历 i ，当前后缀不相等时，

2 重复的子字符串

• 🎈 文档讲解：https://programmercarl.***/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html
• 🎈 视频讲解：https://www.bilibili.***/video/BV1M5411j7Xx/?spm_id_from=333.788&vd_source=d499e7f3a8e68e2b173b1c6f068b2147
• 🎈 做题状态：

2.1 暴力求解

2.2 KMP求解法

3 字符串总结

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

在C语言中，把一个字符串存入一个数组时，也把结束符 '\0’存入数组，并以此作为该字符串是否结束的标志。
在使用 string 的时候直接把他看作一个字符数组会便于理解。