[算法]旋转词问题

题目：

如果一个字符串str，把字符串str前面任意的部分挪到后面形成的字符串叫做str的旋转词。

判断两个字符串是否互为旋转词。

思路：

如果两个字符串的长度不一样，返回false；如果一样，将其中一个字符串*2，比如“abcd”生成新的字符串“abcdabcd”,如果新生成的字符串中含有另一个字符串，那么两个字符串互为旋转词。

在判断一个字符串是否是另一个字符串的子串时，可以使用contains()方法。如果想提高效率，也可以使用KMP算法，可以使时间复杂度为O(N)。

程序：

简单：

public static boolean isRotation(String a, String b) {if (a == null || b == null || a.length() != b.length()) {return false;}String b2 = b + b;return b2.contains(a);}

使用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 getIndexOf(b2, a) != -1;}// KMP Algorithmpublic static int getIndexOf(String s, String m) {if (s.length() < m.length()) {return -1;}char[] ss = s.toCharArray();char[] ms = m.toCharArray();int si = 0;int mi = 0;int[] next = getNextArray(ms);while (si < ss.length && mi < ms.length) {if (ss[si] == ms[mi]) {si++;mi++;} else if (next[mi] == -1) {si++;} else {mi = next[mi];}}return mi == ms.length ? si - mi : -1;}public static int[] getNextArray(char[] ms) {if (ms.length == 1) {return new int[] { -1 };}int[] next = new int[ms.length];next[0] = -1;next[1] = 0;int pos = 2;int cn = 0;while (pos < next.length) {if (ms[pos - 1] == ms[cn]) {next[pos++] = ++cn;} else if (cn > 0) {cn = next[cn];} else {next[pos++] = 0;}}return next;}

转载于:https://www.cnblogs.com/xiaomoxian/p/5158764.html

总结

以上是生活随笔为你收集整理的[算法]旋转词问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。