Java中如何判斷兩個字串是否互為旋轉詞的範例程式碼分享

本篇文章主要介紹了判斷字串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中文網其他相關文章！