一、题目描述

题目描述：给定两字符串A和B，如果能将A从中间某个位置分割为左右两部分字符串（可以为空串），并将左边的字符串移动到右边字符串后面组成新的字符串可以变为字符串B时返回true。

二、算法1（暴力）

解题思路

  1. 暴力考虑翻转后的每个字符串，将其与B串对比，若对比完了都没找到相同的情况，返回false，否则返回true
  2. 为了优化空间复杂度，可以使用双指针算法来作检查，不必每次都创建新字符串，一个指针指向A的新头部，一个指针指向B的头部，先同时向后移动并检查，检查完右边若对上了就检查左边

图片说明

代码实现（C++11）

class Solution {
public:
    bool solve(string A, string B) {
        // 若字符串不等长
        if (A.size() != B.size()) return false;

        // 一开始就相等
        if (A == B) return true;

        int n = A.size();
        for (int i = 1; i < n; i++) {
            // 对比右边
            int j = 0, k = i;
            while (k < n && A[k] == B[j]) k++, j++;
            if (k != n) continue;
            // 对比左边
            k = 0;
            while(j < n && A[k] == B[j]) k++, j++;
            if (j == n) return true;
        }
        return false;
    }
};

时间复杂度：，n为字符串的长度，枚举了所有分界点，每次检查是的，总时间复杂度为
空间复杂度：，使用常数个变量

三、算法2（子串匹配）

解题思路

  1. 对于此类循环问题，有一个经典的方法可以破环成链，即将字符串A再复制一份接在后面，这样每种旋转后的字符串就是新串A+A中的一个子串了，只要确定新串中有无一个字符与B相同即可，就此将问题转换为了经典子串匹配问题
  2. 对于子串匹配问题，我们使用语言提供的库函数，不过一般来说语言提供的函数时间复杂度是的，因此还有一种优秀的子串匹配算法--KMP算法，可以在的时间复杂度匹配子串

代码实现（C++11）

暴力

class Solution {
public:
    bool solve(string A, string B) {
        if (A.size() != B.size()) return false;
        // 新串为 A + A
        string C = A + A;
        // 使用string的find方法
        int pos = C.find(B);

        return pos < C.size();
    }
};

时间复杂度：, n为字符串的长度,暴力找子串的时间复杂度为
空间复杂度：，即新串使用的空间

KMP算法
KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的,感兴趣的读者可以去了解一下具体原理，其核心就是next数组，next[i]表示B以i结尾的非前缀子串与B的前缀能够匹配的最长长度，预处理next数组之后，就能快速检测B是否是A的子串了，具体实现步骤如下：

1.初始化next[1] = j = 0，假设next[1 ~ i - 1]已求出，下面求解next[i].

2.不断尝试扩展匹配长度j，如果扩展失败（下一个字符不相等），令j变为next[j]，直至j为0（应该从新重头开始匹配）.

3.如果能够扩展成功，匹配长度j就增加1，next[i]的值就是j.

代码实现（C++11）

class Solution {
public:
    bool solve(string A, string B) {
        if (A.size() != B.size()) return false;
        // 新串为 A + A
        string C = A + A;
        int n = C.size(), m = B.size();
        // 预处理两个字符串, 在前面加上空字符, 便于实现
        C = ' ' + C, B = ' ' + B;
        vector<int> next(m + 1);
        next[1] = 0;
        for (int i = 2, j = 0; i <= m; i++) {
            while (j && B[i] != B[j + 1]) j = next[j];
            if (B[i] == B[j + 1]) j++;
            next[i] = j;
        }

        for (int i = 1, j = 0; i <= n; i++) {
            while (j && C[i] != B[j + 1]) j = next[j];
            if (C[i] == B[j + 1]) j++;
            if (j == m) return true;
        }

        return false;
    }
};

时间复杂度：, n为C字符串的长度, m为B字符串的长度, 进行次两次遍历，时间复杂度为
空间复杂度：, 辅助数组next使用的空间是的