Exemple de partage de code sur la façon de déterminer si deux chaînes sont des mots en rotation mutuelle en Java

Cet article présente principalement les connaissances pertinentes pour déterminer si chaîne a et b sont des mots en rotation mutuelle et ont une bonne valeur de référence. Jetons un coup d'œil avec l'éditeur ci-dessous.

Mot de rotation : La nouvelle chaîne formée en déplaçant n'importe quelle partie de la chaîne str vers l'arrière est appelée un mot de rotation de la chaîne str.

Par exemple, les mots de rotation de abc incluent abc, acb, cba,...

Jugez si str1 et str2 sont des mots de rotation l'un de l'autre. La solution optimale peut être. que la complexité temporelle est O(n) (n est la longueur de la chaîne)

La méthode est la suivante :

1 Déterminer si les longueurs sont égales.

2. Si les longueurs sont égales, construisez une grande chaîne, str1+str1 (str1+str1 contient tous les mots pivotés de str1)

3. Utilisez l'algorithme KPM pour déterminer si une grande chaîne contient str2

Ce qui suit est l'implémentation spécifique de l'algorithme. Vous devez d'abord comprendre l'algorithme 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;
  }
 }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!