0 引言
1 实现 strStr()
- 🎈 文档讲解：https://programmercarl.com/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数组
- 初始化，两个索引值，分别指向前缀末尾（索引 j ）和后缀末尾（索引 i ）。首先初始化 j=0; next[0] = 0;
- 遍历 i ，当前后缀不相等时，
2 重复的子字符串
- 🎈 文档讲解：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://www.bilibili.com/video/BV1M5411j7Xx/?spm_id_from=333.788&vd_source=d499e7f3a8e68e2b173b1c6f068b2147
- 🎈 做题状态：
2.1 暴力求解
2.2 KMP求解法
3 字符串总结
字符串是若干字符组成的有限序列，也可以理解为是一个字符数组，但是很多语言对字符串做了特殊的规定，接下来我来说一说C/C++中的字符串。
在C语言中，把一个字符串存入一个数组时，也把结束符 '\0’存入数组，并以此作为该字符串是否结束的标志。
在使用 string 的时候直接把他看作一个字符数组会便于理解。
