Compruebe si las strings son rotaciones entre sí o no | conjunto 2

Dadas dos strings s1 y s2, compruebe si s2 es una rotación de s1. 
Ejemplos: 

Input : ABACD, CDABA
Output : True

Input : GEEKS, EKSGE
Output : True

Hemos discutido un enfoque en una publicación anterior que maneja la coincidencia de substrings como un patrón. En esta publicación, utilizaremos la construcción lps (prefijo propio más largo que también es sufijo) del algoritmo KMP , que ayudará a encontrar la coincidencia más larga del prefijo de la string b y el sufijo de la string a. Por lo cual conoceremos el punto de giro , a partir de este punto emparejar los personajes. Si todos los caracteres coinciden, entonces es una rotación, de lo contrario no.
A continuación se muestra la implementación básica del enfoque anterior. 
 

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>

Producción: 
 

1

Complejidad temporal: O(n) 
Espacio auxiliar: O(n)

Publicación traducida automáticamente

Artículo escrito por dmgdeepak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *