题目

如果一个字符串str，把字符串str前面任意的部分挪到后面形成的字符串叫作str的旋转词。比如str=“12345”，str的旋转词有“12345”，“23451”，“34512”，“45123”和“51234”。给定两个字符串a和b，请判断a和b是否互为旋转词。

举例

a=“cdab”，b=“abcd” 返回true

a=“1ab2”，b=“ab12” 返回false

a=“2ab1”，b=“ab12” 返回true

如果a和b长度不一样，那么a和b必然不互为旋转词，可以直接返回false。当a和b长度一样，都为N时，要求解法的时间复杂度为O(N).

如果a和b长度一样，先生成一个大字符串b2，b2是两个字符串b拼在一起的结果，即String b2 = b +b。

java">public class KMP {public static boolean isRotation(String a, String b) {if(a == null || b == null || a.length() != b.length()){return false;}String b2 = b + b;return kmpSearch(b2, a) != -1;}public static int[] compteNext(String pattern) {int[] next = new int[pattern.length()];int j = 0;next[0] = j;for (int i = 1; i < pattern.length(); i++) {while (j > 0 && pattern.charAt(i)!= pattern.charAt(j)) {j = next[j - 1];}if (pattern.charAt(i) == pattern.charAt(j)) {j++;}next[i] = j;}return next;}public static int kmpSearch(String text, String pattern) {int[] next = compteNext(pattern);int i = 0, j = 0;while (i < text.length() && j < pattern.length()) {if (text.charAt(i) == pattern.charAt(j)) {i++;j++;} else if (j > 0) {j = next[j - 1];} else {i++;}}if (j == pattern.length()) {return i - j;} else {return -1;}}public static void main(String[] args) {String text = "cdab";String pattern = "abcd";System.out.println("Pattern found at : " + isRotation(text, pattern));}
}