Java 判断字符串a和b是否互为旋转词
程序员文章站
2024-02-23 23:05:04
旋转词:把字符串str的任意部分移动到后面形成的新字符串叫做字符串str的旋转词。
比如abc的旋转词有 abc,acb,cba,...
判断str1和str2是否互为...
旋转词:把字符串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 判断字符串a和b是否互为旋转词
-
Java 判断字符串a和b是否互为旋转词
-
java多线程定时器和java判断一个时间是否在时间区间内和用正则表达式获取String字符串之间的数据
-
Java中如何判断两个字符串是否互为旋转词的示例代码分享
-
java如何判断字符串是否仅包含数字和字母?
-
Java中如何判断两个字符串是否互为旋转词的示例代码分享
-
java如何判断字符串是否仅包含数字和字母?
-
java多线程定时器和java判断一个时间是否在时间区间内和用正则表达式获取String字符串之间的数据
-
java正则表达式判断字符串是否仅含有数字和字母
-
【JAVA】判断一个字符串是否为回文串!即:一个字符串,从前向后读和从后向前读,都是一个字符串,称为回文串。