day8字符串

有一说一，又是一道题都做不出来的一天
KMP感觉理解了，但是敲不对，有点麻
一道一道记录下
题目：
https://leetcode.cn/problems/reverse-words-in-a-string/
解析：
https://programmercarl.com/0151.翻转字符串里的单词.html#算法公开课

这道题的精髓是消除所有空格：

 string stripSpacess(string& s) {
        int slow = 0;
        int fast = 0;
        while(s.size() > 0 && fast < s.size() && s[fast] == ' ') {
            fast++;
        }
// 这里直接把空格抹掉，前面的空格
        for(; fast < s.size(); fast++) {
            if(fast > 0 && s[fast - 1] == s[fast] && s[fast] == ' ') {
                continue;
            } else {
                s[slow++] = s[fast];
            }
        }
// 在原字符串上处理，我发现字符串的题很喜欢用双指针在原字符串上处理，这里处理完会有些有意思的情况
// 比如："  hello world  "这个case会变成"hello world d "，此时，slow在world后面那个d那里，fast在结尾。
// 此时下面的s[slow - 1]就有作用了，因此这也是为什么需要slow-1去resize了。

            // 去掉字符串末尾的空格
        if (slow > 0 && s[slow - 1] == ' ') {
            s.resize(slow - 1);
        } else {
            s.resize(slow); // 重新设置字符串大小
        }

        return s;
    }

然后整体翻转后，遇到空格和最后的位置，也翻转一下就好了。

题目：
https://kamacoder.com/problempage.php?pid=1065
解析：
https://programmercarl.com/kamacoder/0055.右旋字符串.html
这道题有点遗憾在做完上道题后没做出来，先整体翻转，在翻转0到n，和n到end；

题目：
https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
解析：
https://programmercarl.com/0028.实现strStr.html
leetcode把这个归类为简单，感觉嘲讽拉满。
只能理解使用kmp算法的过程，不知道是怎么想出来的，首先寻找最长相等前后缀，方法如下：

void getNext(int* next, 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;
        }
    }

找到next数组后，我只能说完后的代码是根据next数组，遍历haystack字符串，然后j在needle上移动（根据need数组），
判断从哪里开始比较，我只能说，这个判断方法和寻找next数组很相似，写法很相似。

题目：
https://leetcode.cn/problems/repeated-substring-pattern/description/
解析：
https://programmercarl.com/0459.重复的子字符串.html

先找next数组，然后重点理解下

if (next[len - 1] != -1 && len % (len - (next[len - 1])) == 0) {
            return true;
        }
        return false;

举个例子abcabc，重复的是abc，则next数组的最后一个是3，长度len是6， 6-3=3 6%3 = 0，其实6-3剩余的还是abc，
就等于剩余的就是重复的子项，那字符串一定可以整除它，我只知道是这样，但是怎么想出来的，从无到有想出来的，不知道。