Java 判斷字符串a(chǎn)和b是否互為旋轉(zhuǎn)詞
更新時(shí)間：2017年05月14日 08:50:12 作者：妖久
本篇文章主要介紹了判斷字符串a(chǎn)和b是否互為旋轉(zhuǎn)詞的相關(guān)知識(shí)，具有很好的參考價(jià)值。下面跟著小編一起來(lái)看下吧
旋轉(zhuǎn)詞：把字符串str的任意部分移動(dòng)到后面形成的新字符串叫做字符串str的旋轉(zhuǎn)詞。
比如abc的旋轉(zhuǎn)詞有 abc,acb，cba，...
判斷str1和str2是否互為旋轉(zhuǎn)詞，其最優(yōu)解可以是時(shí)間復(fù)雜度為O（n）（n為字符串的長(zhǎng)度）
方法如下：
1、判斷長(zhǎng)度是否相等
2、長(zhǎng)度相等的話就構(gòu)建大字符串，str1+str1（str1+str1中包含了str1的所有旋轉(zhuǎn)詞）
3、用KPM算法判斷大字符串中是否包含str2
下面是具體算法實(shí)現(xiàn)，必須先了解KPM算法才行
package k;
import java.util.Scanner;
public class test1 {
static int[] next; //next數(shù)組
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(); //獲取輸入的第一個(gè)字符串
str2 = in.next(); //獲取輸入的第二個(gè)字符串
if (str1.length() != str2.length()) //如果長(zhǎng)度不相等，那么就肯定不是互為旋轉(zhuǎn)詞
System.out.println(str1 + "與" + str2 + "不是互為旋轉(zhuǎn)詞");
else
{
str = str1 + str1;
makeNext(); //構(gòu)建next數(shù)組
check(); //判斷是否為旋轉(zhuǎn)詞
}
}
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 + "互為旋轉(zhuǎn)詞");
else
System.out.println(str1 + "與" + str2 + "不是互為旋轉(zhuǎn)詞");
}
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;
}
}
}
以上就是本文的全部?jī)?nèi)容，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，同時(shí)也希望多多支持腳本之家！
相關(guān)文章
詳解Java創(chuàng)建多線程的四種方式以及優(yōu)缺點(diǎn)
這篇文章主要介紹了Java創(chuàng)建多線程的四種方式以及優(yōu)缺點(diǎn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
Jmeter結(jié)構(gòu)體系及運(yùn)行原理順序解析
這篇文章主要介紹了Jmeter結(jié)構(gòu)體系及運(yùn)行原理順序解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09
這篇文章主要介紹了Java中打亂一個(gè)數(shù)組的2種公平算法分享,本文講解了洗牌程序原理、生成隨機(jī)索引交換二種方法并給出示例代碼,需要的朋友可以參考下2015-03-03
Spring Boot實(shí)戰(zhàn)之?dāng)?shù)據(jù)庫(kù)操作的示例代碼
本篇文章主要介紹了Spring Boot實(shí)戰(zhàn)之?dāng)?shù)據(jù)庫(kù)操作的示例代碼，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-01-01
本篇文章向大家介紹springboot2.5.0 整合 redis 配置方法，教大家在pom添加依賴的方法如何調(diào)用redis，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下2021-06-06
Eclipse添加xml文件提示及Hibernate配置學(xué)習(xí)
文件提示功能在開發(fā)過(guò)程中很實(shí)用的，本文實(shí)現(xiàn)了一個(gè)Eclipse添加xml文件提示，感興趣的朋友可以了解下啊，希望本文對(duì)你有所幫助2013-01-01
Spring--國(guó)內(nèi)Java程序員用得最多的框架
前幾年面試最常問(wèn)的且可以順利拿到高薪的技能是Spring，隨著Spring體系的壯大，除非你在簡(jiǎn)歷上添加Spring Boot和Spring Cloud的技能，才可以打動(dòng)面試官，而現(xiàn)在，除非是Spring全家桶的實(shí)戰(zhàn)經(jīng)驗(yàn)，否則難以讓面試官高看2021-06-06
遞歸算法是一種直接或間接地調(diào)用自身的算法,在計(jì)算機(jī)編寫程序中,遞歸算法對(duì)解決一大類問(wèn)題是十分有效的,它往往使算法的描述簡(jiǎn)潔而且易于理解,這篇文章主要給大家介紹了關(guān)于Java遞歸模糊查詢文件的相關(guān)資料,需要的朋友可以參考下2021-11-11
JavaBean和SpringBean的區(qū)別及創(chuàng)建SpringBean方式
這篇文章主要介紹了JavaBean和SpringBean的區(qū)別及創(chuàng)建SpringBean方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-10-10
通過(guò)Java壓縮JavaScript代碼實(shí)例分享
這篇文章主要介紹了通過(guò)Java壓縮JavaScript代碼實(shí)例分享，具有一定參考價(jià)值，需要的朋友可以了解下。2017-12-12