LeetCode：面试题 01.09. 字符串轮转

题目大意： 给定两个字符串，将 s1 进行左移右移后， 能否使得 s2 是 s1 的子串

思路：

1. 扩展 kmp
2. 这是怎么发现问题的本质的， 直接将本身再连接一遍，然后 contains 一下即可.

AC Code

问题本质

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if(s1.length() != s2.length()) return false;
        String s = s1 + s1;
        // abaaba
        return s.contains(s2);
    }
}

---

扩展KMP

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if(s1.length() != s2.length()) return false ;
        if(s1.length() == 0) return true;
        String s = s1 + s1;
        int len2 = s2.length(), len1 = s.length();
        char[] cs1 = s.toCharArray(), cs2 = s2.toCharArray();

        // kmp
        int[] fail = new int[len2];
        Arrays.fill(fail, -1);
        
        // next 数组
        for(int i = 1; i < len2; i++) {
            int j = fail[i - 1];
            while(j != -1 && cs2[i] != cs2[j + 1]) j = fail[j];
            if(cs2[i] == cs2[j + 1]) fail[i] = j + 1;
        }
        //System.out.println(Arrays.toString(fail));

        // 匹配主串
        int j = -1;
        for(int i = 0; i < len1; i++) {
            while(j != -1 && cs1[i] != cs2[j + 1]) j = fail[j] ;
            if(cs1[i] == cs2[j + 1]) j++;

            if(j == len2 - 1) return true ;
        }

        return false;
    }
}