面试金典0109 字符串轮转

题目：

给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）

# 样例1
输入：s1 = "waterbottle", s2 = "erbottlewat"
输出：True
    
# 样例2
输入：s1 = "aa", s2 = "aba"
输出：False

# 提示：
字符串长度在[0, 100000]范围内。

# 说明:
你能只调用一次检查子串的方法吗？

解题方法：

扩充：如果s2是由s1旋转而成，那么将两个s2首尾拼接起来，那么s1一定是拼接后字符串的子串，因此这里用了s.find(s1)?=-1这个函数来判断是否为子串。
- 时间复杂度取决于C++中find()的速度，这里find函数应该是简单使用了匹配算法（见文末），最坏的复杂度为\(O(n*m)\)，但随机字符串均摊后还是\(O(m+n)\)，额外的空间复杂度为\(O(n)\)。
- KMP算法还是值得了解一下原理的（挖坑）

解法一：扩充

字符串拼接：string s = s2 + s2直接用加号即可
字符串匹配：s.find(s1)匹配成功则返回s1在s中的起始位置，否则返回-1

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        string s = s2 + s2;
        int a = s.find(s1);
        // cout << a << "$$" << s <<endl;
        return (s1.size() == s2.size()) && s.find(s1) != -1;
    }
};

字符串匹配暴力算法

遍历主串作为匹配起始点，依次和模式串匹配，匹配成功则返回匹配成功的起始点，不成功返回-1

/**
 * 暴力破解法
 * @param ts 主串
 * @param ps 模式串
 * @return 如果找到，返回在主串中第一个字符出现的下标，否则为-1
 */
public static int bf(String ts, String ps) {
    char[] t = ts.toCharArray();
    char[] p = ps.toCharArray();
    int i = 0; // 主串的位置
    int j = 0; // 模式串的位置
    while (i < t.length && j < p.length) {
       if (t[i] == p[j]) { // 当两个字符相同，就比较下一个
           i++;
           j++;
       } else {
           i = i - j + 1; // 一旦不匹配，i后退
           j = 0; // j归0
       }
    }
    if (j == p.length) {
       return i - j;
    } 
    else {
       return -1;
    }
}

KMP算法（未搞懂）

“利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置”

参考资料:KMP算法