重练算法（代码随想录版） day9 - 字符串part2

今日刷题量：4
当前刷题总量：45
Easy: 26
Mid: 18
Hard: 1

Day9
解题思想
1.整体翻转+部分翻转的多次翻转思想来原地解决字符串左/右旋问题
2.KMP算法思想，比较难理解,记忆getNext模版代码（next数组保持原样不-1版）：

点击查看代码

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

3.对于找重复子串的思路：
（1）把 s 拼接成 t = s + s，去掉首尾字符后，如果 s 还能在 t 中被找到，就说明 s 是由某个子串重复构成的。
（2）如果存在最长相同前后缀next[len - 1],并且数组的长度正好可以被 最长相等前后缀不包含的子串的长度 整除 ，说明该字符串有重复的子字符串。

练习题目

• 151.翻转字符串里的单词（mid）：https://leetcode.cn/problems/reverse-words-in-a-string/
• 卡码网：55.右旋转字符串（easy）：https://kamacoder.com/problempage.php?pid=1065
• 28.找出字符串中第一个匹配项的下标（easy）：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
• 459.重复的子字符串（easy）：https://leetcode.cn/problems/repeated-substring-pattern/description/