右旋字符串

题目代码：

#include <iostream>
using namespace std;
#include <string>

void reverse(string& s, int start, int end){
    while(start <= end){
        swap(s[start], s[end]);
        start++;
        end--;
    }
}

int main(){
    int n = 0;
    string str;
    cin >> n;
    cin >> str;

    int len = str.size();
    reverse(str, 0, len-1);
    reverse(str, 0, n-1);
    reverse(str, n, len-1);
    cout << str <<endl;
    return 0;
}

        也可以用stl的reverse算法，需要在头文件加入#include<algorithm>，还需要注意使用的时候reverse(iterator begin, iterator end)两个参数分别是需要反转的起始迭代器和终止迭代器，并且是左闭右开区间。

        当遇到左旋字符串时，是一样的思路，只不过反转的顺序需要变一下。

strStr() 找出字符串中第一个匹配的下标

题目简述：

        给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

题目代码：

        法一：

class Solution {
public:
    int Compare(string s1, string s2, int s2Start){
        for(int i = 0; i<s1.size(); i++, s2Start++){
            if(s1[i] != s2[s2Start]){
                return -1;
            }
        }
        return 0;
    }

    int strStr(string haystack, string needle) {
        if(needle.size() > haystack.size()){
            return -1;
        }
        for(int i = 0; i<=haystack.size()-needle.size(); i++){
            if(Compare(needle, haystack, i)==0){
                return i ;
            }
        }
        return -1;
    }
};

        时间复杂度O(n*m)，空间复杂度O(1)。思想就是在haystack遍历先找到needle的首字母，一旦找到就开始进行比较，看是否包含有needle字符串，然后还需要记录一开始找到needle首字母的索引值。

        法二：
        可直接使用内置函数 find，时间复杂度O(n*m)，空间复杂度O(1)

        法三：

        用KMP算法:

        九敏啊 我能看懂代码 能看懂next数组求解过程什么的 但是丝毫没有懂这个算法为什么这个样子做能够匹配字符组（已晕）

        带我之后研究了来补充

重复的子字符串

题目描述：

        给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

        

题目代码：

        暴力解法：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = 0;
        for(int i = 0; i<s.size()/2; i++){
            n++;
            string pattern = s.substr(0,n);
            bool re = true;
            for(int j = i+1; j<s.size(); j=j+n){
                if(pattern != s.substr(j, n)){
                    re = false;
                    break;
                }
            }
            if(re){
                return true;
            }
        }
        return false;
    }
};

        时间复杂度O(n^2)，空间复杂度O(1)。外层for循环 i 是子字符串的尾巴，n是子字符串的长度，内层for循环是n长度字符串、n长度字符串与pattern进行比较，一旦不一样，就表明n长度字符串不能重复构成整个字符串，然后就跳出内层的for循环。增加n（增加子字符串长度）再次进行寻找。

        移动匹配：

        如果一个字符串是由某个子串重复多次组成的，那么把它和自己拼接一次得到s+s后，去掉第一个字符和最后一个字符（为了防止找到我们拼接起来的前一个s和后一个s）后，中间部分一定还能找到一个完整的原字符串s。但是如果字符串s本身没有重复的结构，那么在去掉首尾后就肯定不可能再出现字符串s。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string ss = s+s;
        ss.erase(ss.begin());
        ss.erase(ss.end()-1);
        return ss.contains(s);
    }
};

        KMP算法：

        待解答