算法：如何检查字符串是否彼此旋转？|S2

本文概述

• C++
• Java
• C#

给定两个字符串s1和s2, 请检查s2是否为s1的旋转。

例子：

Input : ABACD, CDABA
Output : True

Input : GEEKS, EKSGE
Output : True

我们已经在前面的文章中讨论了一种方法，它将子字符串匹配作为模式处理。在这篇文章中,我们将使用公里算法s有限合伙人(适当的最长前缀也是后缀)建设,这将有助于寻找最长的匹配字符串的前缀和后缀字符串。我们都知道旋转点,从这一点匹配字符。如果所有的字符都匹配，那么它是一个旋转，否则不是。

以下是上述方法的基本实现。

C++

// C++ program to check if
// two strings are rotations
// of each other
#include<bits/stdc++.h>
using namespace std;
bool isRotation(string a, string b)
{
   int n = a.length();
   int m = b.length();
   if (n != m)
     return false ;
 
   // create lps[] that
   // will hold the longest
   // prefix suffix values
   // for pattern
   int lps[n];
 
   // length of the previous
   // longest prefix suffix
   int len = 0;
   int i = 1;
   
   // lps[0] is always 0
   lps[0] = 0;
 
   // the loop calculates
   // lps[i] for i = 1 to n-1
   while (i < n)
   {
     if (a[i] == b[len])
     {
       lps[i] = ++len;
       ++i;
     }
     else
     {
       if (len == 0)
       {
         lps[i] = 0;
         ++i;
       }
       else
       {
         len = lps[len - 1];
       }
     }
   }
 
   i = 0;
 
   // Match from that rotating
   // point
   for ( int k = lps[n - 1];
            k < m; ++k)
   {
     if (b[k] != a[i++])
       return false ;
   }
   return true ;
}
 
// Driver code
int main()
{
   string s1 = "ABACD" ;
   string s2 = "CDABA" ;
   cout << (isRotation(s1, s2) ?
            "1" : "0" );
}
 
// This code is contributed by Chitranayal

Java

// Java program to check if two strings are rotations
// of each other.
import java.util.*;
import java.lang.*;
import java.io.*;
class stringMatching {
     public static boolean isRotation(String a, String b)
     {
         int n = a.length();
         int m = b.length();
         if (n != m)
             return false ;
 
         // create lps[] that will hold the longest
         // prefix suffix values for pattern
         int lps[] = new int [n];
 
         // length of the previous longest prefix suffix
         int len = 0 ;
         int i = 1 ;
         lps[ 0 ] = 0 ; // lps[0] is always 0
 
         // the loop calculates lps[i] for i = 1 to n-1
         while (i < n) {
             if (a.charAt(i) == b.charAt(len)) {
                 lps[i] = ++len;
                 ++i;
             }
             else {
                 if (len == 0 ) {
                     lps[i] = 0 ;
                     ++i;
                 }
                 else {
                     len = lps[len - 1 ];
                 }
             }
         }
 
         i = 0 ;
 
         // match from that rotating point
         for ( int k = lps[n - 1 ]; k < m; ++k) {
             if (b.charAt(k) != a.charAt(i++))
                 return false ;
         }
         return true ;
     }
 
     // Driver code
     public static void main(String[] args)
     {
         String s1 = "ABACD" ;
         String s2 = "CDABA" ;
 
         System.out.println(isRotation(s1, s2) ? "1" : "0" );
     }
}

C#

// C# program to check if
// two strings are rotations
// of each other.
using System;
 
class GFG
{
public static bool isRotation( string a, string b)
{
     int n = a.Length;
     int m = b.Length;
     if (n != m)
         return false ;
 
     // create lps[] that will
     // hold the longest prefix
     // suffix values for pattern
     int []lps = new int [n];
 
     // length of the previous
     // longest prefix suffix
     int len = 0;
     int i = 1;
     
     // lps[0] is always 0
     lps[0] = 0;
 
     // the loop calculates
     // lps[i] for i = 1 to n-1
     while (i < n)
     {
         if (a[i] == b[len])
         {
             lps[i] = ++len;
             ++i;
         }
         else
         {
             if (len == 0)
             {
                 lps[i] = 0;
                 ++i;
             }
             else
             {
                 len = lps[len - 1];
             }
         }
     }
 
     i = 0;
 
     // match from that
     // rotating point
     for ( int k = lps[n - 1]; k < m; ++k)
     {
         if (b[k] != a[i++])
             return false ;
     }
     return true ;
}
 
// Driver code
public static void Main()
{
     string s1 = "ABACD" ;
     string s2 = "CDABA" ;
 
     Console.WriteLine(isRotation(s1, s2) ?
                                      "1" : "0" );
}
}
 
// This code is contributed
// by anuj_67.

输出如下：

1

时间复杂度：O(n)

辅助空间：O(n)

---