首页 > 编程 > Java > 正文

Java 判断字符串a和b是否互为旋转词

2019-11-26 12:18:07
字体:
来源:转载
供稿:网友

旋转词:把字符串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;  } }}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持武林网!

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表