题目

题解

1、类似循环队列的意思

每次逻辑上移动s的一个头到尾去，i代表移动了几个，j代表依次比较
然后进行比较s[(i + j) % n] != goal[j]

class Solution {
public:
    bool rotateString(string s, string goal) {
        int m = s.size(), n = goal.size();
        if (m != n) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            bool flag = true;
            for (int j = 0; j < n; j++) {
                if (s[(i + j) % n] != goal[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return true;
            }
        }
        return false;
    }
};

2、 Kmp复习

就是将s的首尾相连，构成一个长字符串，然后对goal进行kmp匹配

class Solution {
public:
    bool rotateString(string s, string goal) {
        //长度不同肯定错
        if (s.size() != goal.size())return false;
        //首尾相连，我直乎nb
        s += s;
        vector<int> next = get_next(goal);//获取到了next
        //i代表长的s，j代表短的goal
        int i = 1, j = 1;
        //位置小于且等于长度,继续
        while (i <= s.size()&&j <= goal.size()) {
            if (j == 0 || s[i-1] == goal[j-1]) {
                i++; j++;
            }
            else {
                j = next[j];//回溯
            }
        }
        if (j > goal.size()) {//goal匹配完了，说明都在
            return true;
        }
        else {
            return false;
        }
    }
    vector<int> get_next(string T) {
        int i, k;
        int n = T.size();
        vector<int> next(n+1);//第0为为空，且要保证存储size个
        i = 1; k = 0;
        next[i] = 0;
        while (i < n) {
            if (k == 0 || T[i - 1] == T[k - 1]) {//字符串从1开始匹配便于观察，但是实际上要减去
                i++; k++;
                next[i]=k;
            }
            else {
                k = next[k]; //回溯
            }
        }
        return next;
    }
};