算法：一个检查字符串是否相互旋转的程序

本文概述

• 建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
• C ++
• C
• Java
• python
• C#
• 的PHP

给定一个字符串s1和一个字符串s2, 写一个片段说s2是否是s1的旋转？

(例如, 给定s1 = ABCD且s2 = CDAB, 则返回true, 给定s1 = ABCD, 而s2 = ACBD时, 返回false)

算法：

areRotations(str1, str2)

1. Create a temp string and store concatenation of str1 to
       str1 in temp.
                          temp = str1.str1
    2. If str2 is a substring of temp then str1 and str2 are 
       rotations of each other.

    Example:                 
                     str1 = "ABACD"
                     str2 = "CDABA"

     temp = str1.str1 = "ABACDABACD"
     Since str2 is a substring of temp, str1 and str2 are 
     rotations of each other.

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

C ++

// C++ program to check if two given strings
// are rotations of  each other
# include <bits/stdc++.h>
using namespace std;
  
/* Function checks if passed strings (str1
    and str2) are rotations of each other */
bool areRotations(string str1, string str2)
{
    /* Check if sizes of two strings are same */
    if (str1.length() != str2.length())
         return false ;
  
    string temp = str1 + str1; 
   return (temp.find(str2) != string::npos);
}
  
/* Driver program to test areRotations */
int main()
{
    string str1 = "AACD" , str2 = "ACDA" ;
    if (areRotations(str1, str2))
      printf ( "Strings are rotations of each other" );
    else
       printf ( "Strings are not rotations of each other" );
    return 0;
}

C

// C program to check if two given strings are rotations of 
// each other
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
  
/* Function checks if passed strings (str1 and str2)
    are rotations of each other */
int areRotations( char *str1, char *str2)
{
   int size1   = strlen (str1);
   int size2   = strlen (str2);
   char *temp;
   void *ptr;
  
   /* Check if sizes of two strings are same */
   if (size1 != size2)
      return 0;
  
   /* Create a temp string with value str1.str1 */
   temp   = ( char *) malloc ( sizeof ( char )*(size1*2 + 1));
   temp[0] = '' ;
   strcat (temp, str1);
   strcat (temp, str1);
  
   /* Now check if str2 is a substring of temp */
   ptr = strstr (temp, str2);
  
   free (temp); // Free dynamically allocated memory
  
   /* strstr returns NULL if the second string is NOT a
     substring of first string */
   if (ptr != NULL)
     return 1;
   else
     return 0;
}
  
/* Driver program to test areRotations */
int main()
{
     char *str1 = "AACD" ;
     char *str2 = "ACDA" ;
  
     if (areRotations(str1, str2))
        printf ( "Strings are rotations of each other" );
     else
        printf ( "Strings are not rotations of each other" );
  
     getchar ();
     return 0;
}

Java

// Java program to check if two given strings are rotations of 
// each other
  
class StringRotation
{
     /* Function checks if passed strings (str1 and str2)
        are rotations of each other */
     static boolean areRotations(String str1, String str2)
     {
         // There lengths must be same and str2 must be 
         // a substring of str1 concatenated with str1.  
         return (str1.length() == str2.length()) &&
                ((str1 + str1).indexOf(str2) != - 1 );
     }
      
     // Driver method
     public static void main (String[] args)
     {
         String str1 = "AACD" ;
         String str2 = "ACDA" ;
  
         if (areRotations(str1, str2))
             System.out.println( "Strings are rotations of each other" );
         else
             System.out.printf( "Strings are not rotations of each other" );
     }
}
// This code is contributed by  munjal

python

# Python program to check if strings are rotations of
# each other or not
  
# Function checks if passed strings (str1 and str2)
# are rotations of each other
def areRotations(string1, string2):
     size1 = len (string1)
     size2 = len (string2)
     temp = ''
  
     # Check if sizes of two strings are same
     if size1 ! = size2:
         return 0
  
     # Create a temp string with value str1.str1
     temp = string1 + string1
  
     # Now check if str2 is a substring of temp
     # string.count returns the number of occurrences of
     # the second string in temp
     if (temp.count(string2)> 0 ):
         return 1
     else :
         return 0
  
# Driver program to test the above function
string1 = "AACD"
string2 = "ACDA"
  
if areRotations(string1, string2):
     print "Strings are rotations of each other"
else :
     print "Strings are not rotations of each other"
  
# This code is contributed by Bhavya Jain

C#

// C# program to check if two given strings
// are rotations of each other
using System;
  
class GFG {
      
     /* Function checks if passed strings
     (str1 and str2) are rotations of
     each other */
     static bool areRotations(String str1, String str2)
     {
          
         // There lengths must be same and
         // str2 must be a substring of
         // str1 concatenated with str1. 
         return (str1.Length == str2.Length )
              && ((str1 + str1).IndexOf(str2)
                                      != -1);
     }
      
     // Driver method
     public static void Main ()
     {
         String str1 = "FGABCDE" ;
         String str2 = "ABCDEFG" ;
  
         if (areRotations(str1, str2))
             Console.Write( "Strings are"
             + " rotation s of each other" );
         else
             Console.Write( "Strings are "
            + "not rotations of each other" );
     }
}
  
// This code is contributed by nitin mittal.

的PHP

<?php
// Php program to check if 
// two given strings are 
// rotations of each other
  
/* Function checks if passed 
strings (str1 and str2) are 
rotations of each other */
function areRotations( $str1 , $str2 )
{
/* Check if sizes of two
    strings are same */
if ( strlen ( $str1 ) != strlen ( $str2 ))
{
         return false;
}
  
$temp = $str1 + $str1 ; 
if ( $temp . count ( $str2 )> 0)
{
         return true;
}
else
{
     return false;
}
}
  
// Driver code
$str1 = "AACD" ;
$str2 = "ACDA" ;
if (areRotations( $str1 , $str2 ))
{
     echo "Strings are rotations " . 
                   "of each other" ;
}
else
{
     echo "Strings are not " . 
          "rotations of each other" ;
}
  
// This code is contributed
// by Shivi_Aggarwal.
?>

输出如下：

Strings are rotations of each other

使用的库函数：

strstr：

strstr在字符串中找到一个子字符串。

原型：char * strstr(const char * s1, const char * s2);

看到

http://www.lix.polytechnique.fr/Labo/Leo.Liberti/public/computing/prog/c/C/MAN/strstr.htm

更多细节

strcat：

strncat连接两个字符串

原型：char * strcat(char * dest, const char * src);

看到

http://www.lix.polytechnique.fr/Labo/Leo.Liberti/public/computing/prog/c/C/MAN/strcat.htm

更多细节

时间复杂度：

此问题的时间复杂度取决于strstr函数的实现。

如果使用KMP匹配器执行strstr, 则上述程序的复杂度为(-)(n1 + n2), 其中n1和n2是字符串的长度。 KMP匹配器花费(-)(n)时间在长度为n的字符串中找到一个子字符串, 其中子字符串的长度假定小于该字符串。