本篇文章主要介紹了判斷字串a和b是否互為旋轉詞的相關知識,具有很好的參考價值。下面跟著小編一起來看下吧
旋轉字:把字串str的任何部分移到後面形成的新字串叫做字串str的旋轉字。
例如abc的旋轉詞有abc,acb,cba,...
#判斷str1和str2是否互為旋轉詞,其最優解可以是時間複雜度為O(n)(n為字串的長度)
方法如下:
#1、判斷長度是否相等
2、長度相等的話就建構大字串,str1+str1(str1+str1中包含了str1的所有旋轉字)
3、用KPM演算法判斷大字串中是否包含str2
以下是具體演算法實現,必須先了解KPM演算法才行
package k; import java.util.Scanner; public class test1 { static int[] next; //next数组 static String str1; //字符串str1 static String str2; //字符串str2 static String str; //字符串str=str1+str1 public static void main(String[] args) { Scanner in = new Scanner(System.in); str1 = in.next(); //获取输入的第一个字符串 str2 = in.next(); //获取输入的第二个字符串 if (str1.length() != str2.length()) //如果长度不相等,那么就肯定不是互为旋转词 System.out.println(str1 + "与" + str2 + "不是互为旋转词"); else { str = str1 + str1; makeNext(); //构建next数组 check(); //判断是否为旋转词 } } private static void check() { int i = 0; int j = 0; while (i < str2.length() && j < str.length()) if (i == -1 || str2.charAt(i) == str.charAt(j)) { i++; j++; } else { i = next[i]; } if (i >= str2.length()) System.out.println(str1 + "与" + str2 + "互为旋转词"); else System.out.println(str1 + "与" + str2 + "不是互为旋转词"); } private static void makeNext() { next = new int[str2.length()]; int i = 0; int k = -1; next[0] = -1; while (i < str2.length() - 1) { while (k >= 0 && str2.charAt(i) != str2.charAt(k)) k = next[k]; i++; k++; if (str2.charAt(i) == str2.charAt(k)) next[i] = next[k]; else next[i] = k; } } }
以上是Java中如何判斷兩個字串是否互為旋轉詞的範例程式碼分享的詳細內容。更多資訊請關注PHP中文網其他相關文章!