今日主要学习字符串翻转的进阶以及MKP算法，重点在于理解KMP算法的原理，学会使用KMP算法。KMP算法理论知识参考：KMP算法|代码随想录

151.翻转字符串里的单词

思路：可以把这个题目拆分成三个部分，首先把字符串里面多余的空格去掉，首尾不要有空格，其次将字符串整体翻转，再识别单词，将单词挨个翻转，就实现了翻转字符串的操作。

我的代码：

class Solution {
public:
    void reverse(string& s,int start,int end)
    {
        for(int i=start,j=end;i<j;i++,j--)
        {
            swap(s[i],s[j]);
        }
    }
    void removespace(string& s)
    {
        int slow=0;
        for(int i=0;i<s.size();i++)
        {
           if(i==0&&s[i]==' ')
           {
            while(s[i]==' ') i++;
           }
           else if(s[i]!=' ') 
           {
            while(i<s.size()&&s[i]!=' ') s[slow++]=s[i++];
           }
           else {
            s[slow++]=s[i++];
            while(i<s.size()&&s[i]==' ') i++;
           }
           i--;
        }
        while(s[--slow]==' ');
        s.resize(slow+1);
    }
    string reverseWords(string s) {
        removespace(s);
        reverse(s,0,s.size()-1);
        int start=0;
       for(int i=0;i<=s.size();i++)
       {
        if(i==s.size()||s[i]==' ')
        {
            reverse(s,start,i-1);
            start=i+1;
        }
       }
       return s;
    }
};

难点：本题难点主要在于去掉空格的这个操作中，我写的时候逻辑没有很清晰导致带起看起来缝缝补补的，不好看且长，因为开头和结尾的空格是要另外考虑的，所以这里提供一个简介思路清晰的版本。

void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
    int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
    for (int i = 0; i < s.size(); ++i) { //
        if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
            if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
            while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
                s[slow++] = s[i++];
            }
        }
    }
    s.resize(slow); //slow的大小即为去除多余空格后的大小。
}

55.右旋转字符串

思路：这道题好像的思路是开一个一样大的空间，然后把字符串复制一份，然后按照这个移动顺序往原来的数组里面填，但是空间复杂度太大。简化思路就是先整体翻转字符串，这样后n个字符就变成了前n个字符，然后再对前n个字符和剩下的字符分别翻转，其实是翻转字符串的另一个应用。

我的代码：

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    string s;
    cin>>n;
    cin>>s;
    reverse(s.begin(),s.end());
    reverse(s.begin(),s.begin()+n);
    reverse(s.begin()+n,s.end());
    cout<<s<<endl;
}

28. 实现 strStr()

思路:最直观的解法的是：枚举原串中的每个字符作为起点，每次从原串的起点和匹配串的首位开始尝试匹配，匹配成功则返回本次匹配的原串起点，匹配失败则枚举原串的下一个起点，重新尝试匹配。但这个时间复杂度是O(n)，如果要优化，就要用到我们的主角：KMP算法。

暴力算法代码（力扣宫水三叶题解）：

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        for(int i = 0; i <= n - m; i++){
            int j = i, k = 0; 
            while(k < m and s[j] == p[k]){
                j++;
                k++;
            }
            if(k == m) return i;
        }
        return -1;
    }
};

学KMP算法，最核心是要理解前缀表，怎么构造前缀表，怎么运用前缀表是关键。前缀表的关键是next数组，而next数组的关键是j的回退还有next[i]的更新，注意j的双重身份：后缀的下标，前缀的长度。

其实学KMP算法一定要看着动图脑子里走一遍，我今天也是第一遍学，自己写这个代码还是比较生疏，但是多写几遍就会有点感觉。

代码：

class Solution {
public:
    void getnext(const string& s,int* next)
    {
        int j=-1;
        next[0]=-1;
        for(int i=1;i<s.size();i++)
        {
            while(j>=0&&s[i]!=s[j+1]) j=next[j];
            if(s[i]==s[j+1]) j++;
            next[i]=j;
        }
    }
    int strStr(string haystack, string needle) {
        int m=haystack.size();
        int n=needle.size();
        if(n==0) return 0;
        vector<int> next(n);
        getnext(needle,&next[0]);
        int j=-1;
        for(int i=0;i<m;i++)
        {
           while(j>=0&&haystack[i]!=needle[j+1]) j=next[j];
           if(haystack[i]==needle[j+1]) j++;
           if(j==n-1) return i-n+1;
        }
        return -1;
    }
};

注意：这里next数组是统一减一之后的，只是表示方式的不同，本质没区别，我写下来感觉这样字写确实会好写一些。

459.重复的子字符串

思路一：暴力枚举

参考力扣官方题解，不过多解释：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for (int i = 1; i * 2 <= n; ++i) {
            if (n % i == 0) {
                bool match = true;
                for (int j = i; j < n; ++j) {
                    if (s[j] != s[j - i]) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }
};

思路二：移动匹配

核心在于：判断字符串s是否由重复子串组成，只要两个s拼接在一起，去除首尾里面还出现一个s的话，就说明是由重复子串组成。

这个结论是需要严格证明的，可以看力扣官方题解正确性部分，但是直观上这个结论挺好理解的。

代码：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
        if (t.find(s) != std::string::npos) return true; // r
        return false;
    }
};

问题:这里用到的库函数find其实时间复杂度也有O(n),想要高效查找字符串还是要用到KMP算法，所以把这里面find函数换成KMP算法函数效率会更高。

思路三：KMP算法

这个办法本质在于：当最长相等前后缀不包含的子串的长度 可以被 字符串s的长度整除，那么不包含的子串 就是s的最小重复子串。

分步来说也就是要证明：

充分条件：如果字符串s是由重复子串组成，那么 最长相等前后缀不包含的子串 一定是 s的最小重复子串。

必要条件：如果字符串s的最长相等前后缀不包含的子串 是 s最小重复子串，那么 s是由重复子串组成。

证明可以看代码随想录：重复的子字符串|代码随想录

代码：

class Solution {
public:
    void getnext(string& s,int *next)
    {
        int j=-1;
        next[0]=-1;
        for(int i=1;i<s.size();i++)
        {
            while(j>=0&&s[i]!=s[j+1])
            {
                j=next[j];
            }
            if(s[i]==s[j+1]) j++;
            next[i]=j;
        }
    }
    bool repeatedSubstringPattern(string s) {
       if(s.size()==0) return false;
       vector<int> next(s.size());
       getnext(s,&next[0]);
       if(next[s.size()-1]!=-1&&s.size()%(s.size()-next[s.size()-1]-1)==0) return true;
       return false;
    }
};

今日总结

今天强度真的很大，学习了一个目前我接触到最难的算法，但是还是坚持吧这些题目理解了，但是在这里面一些结论的证明我还不是特别懂，不过KMP框架多写几遍还是能记住的。至此字符串也完结了，继续加油！！