题目描述

对于一个字符串来说，定义一次循环移位操作为：将字符串的第一个字符移动到末尾形成新的字符串。

给定两个字符串s1和s2，要求判定其中一个字符串是否是另一字符串通过若干次循环移位后的新字符串的子串。

例如CDAA是由AABCD两次移位后产生的新串BCDAA的子串，而ABCD与ACBD则不能通过多次移位来得到其中一个字符串是新串的子串。

样例

输入样例：
AABCD CDAA
输出样例：
true

算法1

若s2是s1通过循环移位得到的子串，首先s2长度一定要不大于s1长度。

此处有个规律：对s1做循环移位所得到的字符串都是字符串s1s1的子串。
如果s2是s1通过若干次循环移位后的新字符串的子串，那么s2也必定是字符串s1s1的子串。
所以只需要构建字符串s1s1,然后判断s2是否为s1s1的子串即可。

时间复杂度 为子串匹配算法KMP的时间复杂度 O(n+m)

参考文献 编程之美

Java 代码

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.next();
        String str2 = sc.next();
        if (str1.length()>=str2.length()){
            System.out.println(f(str1, str2));
        }else {
            System.out.println(f(str2, str1));
        }
    }

    public static boolean f(String str1, String str2) {

        StringBuilder s = new StringBuilder(str1).append(str1);
        return s.toString().contains(str2);
    }
}