检查字符串是否相互旋转|设置2-yiteyi-C++库

给定两个字符串s1和s2，检查s2是否是s1的旋转。 例如：

null

Input : ABACD, CDABAOutput : TrueInput : GEEKS, EKSGEOutput : True

我们讨论了一种方法早期的将子字符串匹配作为模式处理的post。在本文中，我们将使用 KMP算法的lps （最长的正确前缀，也就是后缀）构造，这将有助于找到字符串b的前缀和字符串a的后缀的最长匹配。通过它，我们将知道 旋转点 ，从这一点上匹配字符。如果所有字符都匹配，则这是一个旋转，否则不是。下面是上述方法的基本实现。

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"                                     );                       
                                                 }                       
                         }                       

Python3

                         # Python program to check if                       
                         # two strings are rotations                       
                         # of each other                       
                         def                                     isRotation(a:                                     str                                     , b:                                     str                                     )                                     -                                     >                                     bool                                     :                       
                                                 n                                     =                                     len                                     (a)                       
                                                 m                                     =                                     len                                     (b)                       
                                                 if                                     (n !                                     =                                     m):                       
                                                 return                                     False                       
           
                                                 # create lps[] that                       
                                                 # will hold the longest                       
                                                 # prefix suffix values                       
                                                 # for pattern                       
                                                 lps                                     =                                     [                                     0                                     for                                     _                                     in                                     range                                     (n)]                       
           
                                                 # length of the previous                       
                                                 # longest prefix suffix                       
                                                 length                                     =                                     0                       
                                                 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[length]):                       
                                                 length                                     +                                     =                                     1                       
                                                 lps[i]                                     =                                     length                       
                                                 i                                     +                                     =                                     1                       
                                                 else                                     :                       
                                                 if                                     (length                                     =                                     =                                     0                                     ):                       
                                                 lps[i]                                     =                                     0                       
                                                 i                                     +                                     =                                     1                       
                                                 else                                     :                       
                                                 length                                     =                                     lps[length                                     -                                     1                                     ]                       
                                                 i                                     =                                     0                       
           
                                                 # Match from that rotating                       
                                                 # point                       
                                                 for                                     k                                     in                                     range                                     (lps[n                                     -                                     1                                     ], m):                       
                                                 if                                     (b[k] !                                     =                                     a[i]):                       
                                                 return                                     False                       
                                                 i                                     +                                     =                                     1                       
                                                 return                                     True                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 s1                                     =                                     "ABACD"                       
                                                 s2                                     =                                     "CDABA"                       
                                                 print                                     (                                     "1"                                     if                                     isRotation(s1, s2)                                     else                                     "0"                                     )                       
           
                         # This code is contributed by sanjeev2552                       

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.                       

Javascript

                         <script>                       
           
                         // javascript program to check if two strings are rotations                       
                         // of each other.                       
                         function                                     isRotation(a, b)                       
                         {                       
                                                 var                                     n = a.length;                       
                                                 var                                     m = b.length;                       
                                                 if                                     (n != m)                       
                                                 return                                     false                                     ;                       
           
                                                 // create lps that will hold the longest                       
                                                 // prefix suffix values for pattern                       
                                                 var                                     lps = Array.from({length: n}, (_, i) => 0);                       
           
                                                 // length of the previous longest prefix suffix                       
                                                 var                                     len = 0;                       
                                                 var                                     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                                     (k = lps[n - 1]; k < m; ++k) {                       
                                                 if                                     (b.charAt(k) != a.charAt(i++))                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver code                       
                         var                                     s1 =                                     "ABACD"                                     ;                       
                         var                                     s2 =                                     "CDABA"                                     ;                       
                         document.write(isRotation(s1, s2) ?                                     "1"                                     :                                     "0"                                     );                       
           
                         // This code is contributed by shikhasingrajput.                       
                         </script>                       

输出：

时间复杂性： O（n） 辅助空间： O（n）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章