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

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持我们！

赞 (0)

相关推荐

  • C语言左旋转字符串与翻转字符串中单词顺序的方法

    左旋转字符串 题目: 定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部. 如把字符串 abcdef  左旋转 2  位得到字符串 cdefab.请实现字符串左旋转的函数. 要求时间对长度为 n  的字符串操作的复杂度为 O(n),辅助内存为 O(1). 分析: 网上看到解法很多种,就不详细说明了. 我采用的是数组不对称的交换时间复杂度应该是O(n). 代码实现(GCC编译通过): #include "stdio.h" #include "stdlib.h&q

  • 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 j

  • java判断字符串中是否包含中文并过滤中文

    java判断字符串中是否包含中文并过滤掉中文,具体内容如下 1.判断字符串中是否包含中文方法封装 /** * 判断字符串中是否包含中文 * @param str * 待校验字符串 * @return 是否为中文 * @warn 不能校验是否为中文标点符号 */ public static boolean isContainChinese(String str) { Pattern p = Pattern.compile("[\u4e00-\u9fa5]"); Matcher m = p

  • java判断字符串是否为数字的方法小结

    本文实例总结了java判断字符串是否为数字的方法.分享给大家供大家参考,具体如下: 方法一:用JAVA自带的函数 public static boolean isNumeric(String str){ for (int i = str.length();--i>=0;){ if (!Character.isDigit(str.charAt(i))){ return false; } } return true; } 方法二:用正则表达式 public static boolean isNume

  • java 判断字符串是否包含子串的方法

    java 判断字符串是否包含子串的方法 方法一: String str1 = "nihaoksdoksad "; String str2 = "ok "; int total = 0; for (String tmp = str1; tmp != null&&tmp.length()> =str2.length();){ if(tmp.indexOf(str2) == 0){ total ++; } tmp = tmp.substring(1)

  • java判断字符串String是否为空问题浅析

    一.判断一个字符串str不为空的方法有: 1.str == null;2."".equals(str);3.str.length <= 0;4.str.isEmpty();注意:length是属性,一般集合类对象拥有的属性,取得集合的大小.            例如:数组.length就是取得数组的长度.          length()是方法,一般字符串类对象有该方法,也是取得字符串长度.            例如:字符串.length();说明:  1.null表示这个

  • java判断字符串是否有逗号的方法

    如下所示: if(str.indexOf(",") >= 0) System.out.println("字符串中有逗号"); 以上这篇java判断字符串是否有逗号的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • Java 判断字符串中是否包含中文的实例详解

    Java 判断字符串中是否包含中文的实例详解

    Java 判断字符串中是否包含中文的实例详解 Java判断一个字符串是否有中文是利用Unicode编码来判断,因为中文的编码区间为:0x4e00--0x9fbb, 不过通用区间来判断中文也不非常精确,因为有些中文的标点符号利用区间判断会得到错误的结果.而且利用区间判断中文效率也并不高,例如:str.substring(i, i + 1).matches("[\\一-\\?]+"),就需要遍历整个字符串,如果字符串太长效率非常低,而且判断标点还会错误.这里提高 一个高效准确的判断方法,使

  • Java判断字符串是否含有乱码实例代码

    具体代码如下所示: /** * 判断字符是否是中文 * * @param c 字符 * @return 是否是中文 */ public static boolean isChinese(char c) { Character.UnicodeBlock ub = Character.UnicodeBlock.of(c); if (ub == Character.UnicodeBlock.CJK_UNIFIED_IDEOGRAPHS || ub == Character.UnicodeBlock.C

  • Java判断字符串是否是整数或者浮点数的方法

    如下所示: //判断整数(int) private boolean isInteger(String str) { if (null == str || "".equals(str)) { return false; } Pattern pattern = Pattern.compile("^[-\\+]?[\\d]*$"); return pattern.matcher(str).matches(); } //判断浮点数(double和float) private

  • java 判断字符串中是否有重复字符的示例

    如下所示: /** * 判断字符串是否包含重复字符 * @param str * @return */ public static boolean containRepeatChar(String str){ if(str==null||str.isEmpty()){ return false; } char[] elements=str.toCharArray(); for(char e:elements){ if(str.indexOf(e)!=str.lastIndexOf(e)){ re

随机推荐