두 문자열이 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!