Example code sharing on how to determine whether two strings are mutually rotated words in Java

This article mainly introduces the relevant knowledge to determine whether string a and b are mutually rotated words, and has a good reference value. Let’s take a look at it with the editor

Rotation word: The new string formed by moving any part of the string str to the back is called the rotation word of the string str.

For example, the rotation words of abc include abc, acb, cba,...

To determine whether str1 and str2 are rotation words for each other, the optimal solution can be that the time complexity is O(n) (n is the length of the string)

The method is as follows:

1. Determine whether the lengths are equal

2. If the lengths are equal, construct a large string, str1+str1 (str1+str1 contains all the rotated words of str1)

3. Use KPM algorithm to determine whether a large string contains str2

The following is the specific algorithm implementation. You must first understand the KPM algorithm

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;
  }
 }
}

The above is the detailed content of Example code sharing on how to determine whether two strings are mutually rotated words in Java. For more information, please follow other related articles on the PHP Chinese website!