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

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 = newhttp:// 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++;

} elhttp://se {

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) != stOLTpaHXwr2.charAt(k))

k = next[k];

i++;

k++;

if (str2.charAt(i) == str2.charAt(k))

next[i] = next[k];

else

next[i] = k;

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。