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

所属分类: 软件编程 / java 阅读数: 37
收藏 0 赞 0 分享

旋转词:把字符串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 concurrency之锁_动力节点Java学院整理

这篇文章主要为大家详细介绍了Java concurrency之锁的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
收藏 0 赞 0 分享

Java8新特性之StampedLock_动力节点Java学院整理

本文从synchronized、Lock到Java8新增的StampedLock进行对比分析,对Java8新特性之StampedLock相关知识感兴趣的朋友一起看看吧
收藏 0 赞 0 分享

Java8新特性之lambda的作用_动力节点Java学院整理

我们期待了很久lambda为java带来闭包的概念,但是如果我们不在集合中使用它的话,就损失了很大价值。现有接口迁移成为lambda风格的问题已经通过default methods解决了,在这篇文章将深入解析Java集合里面的批量数据操作解开lambda最强作用的神秘面纱。
收藏 0 赞 0 分享

Java8新特性之Base64详解_动力节点Java学院整理

这篇文章主要为大家详细介绍了Java8新特性之Base64的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
收藏 0 赞 0 分享

Java8新特性之JavaFX 8_动力节点Java学院整理

这篇文章主要介绍了Java8新特性之JavaFX 8的相关知识,非常不错,具有参考借鉴价值,需要的朋友参考下吧
收藏 0 赞 0 分享

将本地jar包安装进入maven仓库(实现方法)

下面小编就为大家带来一篇将本地jar包安装进入maven仓库(实现方法)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
收藏 0 赞 0 分享

浅谈Java finally语句到底是在return之前还是之后执行(必看篇)

下面小编就为大家带来一篇浅谈Java finally语句到底是在return之前还是之后执行(必看篇)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
收藏 0 赞 0 分享

基于Java并发容器ConcurrentHashMap#put方法解析

下面小编就为大家带来一篇基于Java并发容器ConcurrentHashMap#put方法解析。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
收藏 0 赞 0 分享

详解Spring Boot Profiles 配置和使用

本篇文章主要介绍了详解Spring Boot Profiles 配置和使用,具有一定的参考价值,有兴趣的可以了解一下
收藏 0 赞 0 分享

详解Spring Boot 属性配置和使用

本篇文章主要介绍了详解Spring Boot 属性配置和使用,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
收藏 0 赞 0 分享
查看更多