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

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

转载作者：qq735679552 更新时间：2022-09-27 22:32:09

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章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; 
        
         } 
        
         } 
        
         }