Beispielcode-Sharing zur Bestimmung, ob zwei Zeichenfolgen in Java gegeneinander rotierte Wörter sind

Dieser Artikel stellt hauptsächlich das relevante Wissen vor, um zu bestimmen, ob Zeichenfolge a und b gegenseitig rotierte Wörter sind und einen guten Referenzwert haben. Schauen wir es uns mit dem Editor unten an

Rotationswort: Die neue Zeichenfolge, die durch das Verschieben eines beliebigen Teils der Zeichenfolge str nach hinten entsteht, wird als Rotationswort der Zeichenfolge str bezeichnet.

Zu den Rotationswörtern von abc gehören beispielsweise abc, acb, cba, ...

Beurteilen Sie, ob str1 und str2 Rotationswörter voneinander sind. Die optimale Lösung kann sein dass die Zeitkomplexität O(n) ist (n ist die Länge der Zeichenfolge)

Die Methode ist wie folgt:

1 Bestimmen Sie, ob die Längen gleich sind

2. Wenn die Längen gleich sind, konstruieren Sie eine große Zeichenfolge, str1+str1 (str1+str1 enthält alle gedrehten Wörter von str1)

3. Verwenden Sie den KPM-Algorithmus, um zu bestimmen, ob eine große Zeichenfolge str2 enthält

Das Folgende ist die spezifische Algorithmusimplementierung. Sie müssen zuerst den KPM-Algorithmus verstehen

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

Das obige ist der detaillierte Inhalt vonBeispielcode-Sharing zur Bestimmung, ob zwei Zeichenfolgen in Java gegeneinander rotierte Wörter sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!