Cuente el número de formas de convertir la string S a T realizando K cambios cíclicos

Posted on by Rudeus Greyrat

Dadas dos strings S y T y un número K , la tarea es contar el número de formas de convertir la string S en la string T realizando K desplazamientos cíclicos . 
 

El cambio cíclico se define como la string S que se puede dividir en dos partes no vacías X + Y y en una operación podemos transformar S a Y + X desde X + Y.

Nota: Dado que la cuenta puede ser muy grande, imprima la respuesta al módulo 10 9 + 7 .
Ejemplos: 
 

Entrada: S = “ab”, T = “ab”, K = 2 
Salida: 1 
Explicación: 
La única manera de hacer esto es convertir [ab a ba] en el primer movimiento y luego [ba a ab] en el segundo Muevete. 
Entrada: S = “ababab”, T = “ababab”, K = 1 
Salida: 2 
Explicación: 
Una forma posible de convertir S a T en un solo movimiento es [ab | abab] -> [ababab] , la segunda forma es [abab | ab] -> [ababab] . Así que hay un total de dos maneras. 
 

Enfoque: Este problema se puede resolver usando Programación Dinámica . Llamemos a un cambio cíclico ‘bueno’ si al final estamos en la string T y viceversa para ‘malo’ . A continuación se muestran los pasos:
 

  1. Calcule previamente el número de cambios cíclicos buenos (indicados por a) y malos (indicados por b).
  2. Inicialice dos arreglos de dp tales que dp1[i] denote la cantidad de formas de llegar a un buen cambio en i move y dp2[i] denote la cantidad de formas de llegar a un mal cambio en i move .
  3. Para la transición, solo nos preocupa el estado anterior, es decir, (i – 1)-ésimo estado y la respuesta a esta pregunta es dp1[K] .
  4. Entonces, la cantidad de formas de alcanzar un buen estado en los movimientos i es igual a la cantidad de formas de lograr un buen cambio en los movimientos i-1 multiplicado por (a-1) (ya que el último cambio también es bueno)
  5. Entonces, el número de formas de llegar a un mal cambio en los movimientos i-1 multiplicado por (a) (ya que el próximo movimiento puede ser cualquiera de los buenos cambios).

A continuación se muestra la relación de recurrencia para los turnos buenos y malos:
 

Así que para buenos turnos tenemos: 
dp1[i]= dp1[i-1]*(a-1) + dp2[i-1]*a
Del mismo modo, para malos turnos tenemos: 
dp2[i]=dp1[i-1]*b + dp2[i-1]*(b-1)
 

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define mod 10000000007
 
// Function to count number of ways to
// convert string S to string T by
// performing K cyclic shifts
long long countWays(string s, string t,
                    int k)
{
    // Calculate length of string
    int n = s.size();
 
    // 'a' is no of good cyclic shifts
    // 'b' is no of bad cyclic shifts
    int a = 0, b = 0;
 
    // Iterate in the string
    for (int i = 0; i < n; i++) {
 
        string p = s.substr(i, n - i)
                + s.substr(0, i);
 
        // Precompute the number of good
        // and bad cyclic shifts
        if (p == t)
            a++;
        else
            b++;
    }
 
    // Initialize two dp arrays
    // dp1[i] to store the no of ways to
    // get to a good shift in i moves
 
    // dp2[i] to store the no of ways to
    // get to a bad shift in i moves
    vector<long long> dp1(k + 1), dp2(k + 1);
 
    if (s == t) {
        dp1[0] = 1;
        dp2[0] = 0;
    }
    else {
        dp1[0] = 0;
        dp2[0] = 1;
    }
 
    // Calculate good and bad shifts
    for (int i = 1; i <= k; i++) {
 
        dp1[i]
            = ((dp1[i - 1] * (a - 1)) % mod
            + (dp2[i - 1] * a) % mod)
            % mod;
 
        dp2[i]
            = ((dp1[i - 1] * (b)) % mod
            + (dp2[i - 1] * (b - 1)) % mod)
            % mod;
    }
 
    // Return the required number of ways
    return dp1[k];
}
 
// Driver Code
int main()
{
    // Given Strings
    string S = "ab", T = "ab";
 
    // Given K shifts required
    int K = 2;
 
    // Function Call
    cout << countWays(S, T, K);
    return 0;
}

Java

// Java program for above approach
class GFG{
     
static long mod = 10000000007L;
 
// Function to count number of ways to
// convert string S to string T by
// performing K cyclic shifts
static long countWays(String s, String t,
                    int k)
{
     
    // Calculate length of string
    int n = s.length();
 
    // 'a' is no of good cyclic shifts
    // 'b' is no of bad cyclic shifts
    int a = 0, b = 0;
 
    // Iterate in the string
    for(int i = 0; i < n; i++)
    {
    String p = s.substring(i, n - i) +
                s.substring(0, i);
         
    // Precompute the number of good
    // and bad cyclic shifts
    if (p == t)
        a++;
    else
        b++;
    }
 
    // Initialize two dp arrays
    // dp1[i] to store the no of ways to
    // get to a good shift in i moves
 
    // dp2[i] to store the no of ways to
    // get to a bad shift in i moves
    long dp1[] = new long[k + 1];
    long dp2[] = new long[k + 1];
 
    if (s == t)
    {
        dp1[0] = 1;
        dp2[0] = 0;
    }
    else
    {
        dp1[0] = 0;
        dp2[0] = 1;
    }
 
    // Calculate good and bad shifts
    for(int i = 1; i <= k; i++)
    {
    dp1[i] = ((dp1[i - 1] * (a - 1)) % mod +
                (dp2[i - 1] * a) % mod) % mod;
    dp2[i] = ((dp1[i - 1] * (b)) % mod +
                (dp2[i - 1] * (b - 1)) % mod) % mod;
    }
 
    // Return the required number of ways
    return dp1[k];
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given Strings
    String S = "ab", T = "ab";
 
    // Given K shifts required
    int K = 2;
 
    // Function Call
    System.out.print(countWays(S, T, K));
}
}
 
// This code is contributed by Pratima Pandey

Python3

# Python3 program for the above approach
mod = 1000000007
 
# Function to count number of ways
# to convert string S to string T by
# performing K cyclic shifts
def countWays(s, t, k):
     
    # Calculate length of string
    n = len(s)
     
    # a is no. of good cyclic shifts
    # b is no. of bad cyclic shifts
    a = 0
    b = 0
     
    # Iterate in string
    for i in range(n):
        p = s[i : n - i + 1] + s[: i + 1]
         
        # Precompute the number of good
        # and bad cyclic shifts
        if(p == t):
            a += 1
        else:
            b += 1
             
    # Initialize two dp arrays
    # dp1[i] to store the no of ways to
    # get to a goof shift in i moves
     
    # dp2[i] to store the no of ways to
    # get to a bad shift in i moves
    dp1 = [0] * (k + 1)
    dp2 = [0] * (k + 1)
     
    if(s == t):
        dp1[0] = 1
        dp2[0] = 0
    else:
        dp1[0] = 0
        dp2[0] = 1
         
    # Calculate good and bad shifts    
    for i in range(1, k + 1):
        dp1[i] = ((dp1[i - 1] * (a - 1)) % mod +
                (dp2[i - 1] * a) % mod) % mod
 
        dp2[i] = ((dp1[i - 1] * (b)) % mod +
                (dp2[i - 1] * (b - 1)) % mod) % mod
                     
    # Return the required number of ways
    return(dp1[k])
     
# Driver Code
 
# Given Strings
S = 'ab'
T = 'ab'
 
# Given K shifts required
K = 2
 
# Function call
print(countWays(S, T, K))
 
# This code is contributed by Arjun Saini

C#

// C# program for the above approach
using System;
 
class GFG{
     
static long mod = 10000000007L;
 
// Function to count number of ways to
// convert string S to string T by
// performing K cyclic shifts
static long countWays(string s, string t,
                      int k)
{
     
    // Calculate length of string
    int n = s.Length;
 
    // 'a' is no of good cyclic shifts
    // 'b' is no of bad cyclic shifts
    int a = 0, b = 0;
 
    // Iterate in the string
    for(int i = 0; i < n; i++)
    {
        string p = s.Substring(i, n - i) +
                   s.Substring(0, i);
         
        // Precompute the number of good
        // and bad cyclic shifts
        if (p == t)
            a++;
        else
            b++;
    }
 
    // Initialize two dp arrays
    // dp1[i] to store the no of ways to
    // get to a good shift in i moves
 
    // dp2[i] to store the no of ways to
    // get to a bad shift in i moves
    long []dp1 = new long[k + 1];
    long []dp2 = new long[k + 1];
 
    if (s == t)
    {
        dp1[0] = 1;
        dp2[0] = 0;
    }
    else
    {
        dp1[0] = 0;
        dp2[0] = 1;
    }
 
    // Calculate good and bad shifts
    for(int i = 1; i <= k; i++)
    {
        dp1[i] = ((dp1[i - 1] * (a - 1)) % mod +
                  (dp2[i - 1] * a) % mod) % mod;
        dp2[i] = ((dp1[i - 1] * (b)) % mod +
                  (dp2[i - 1] * (b - 1)) % mod) % mod;
    }
 
    // Return the required number of ways
    return dp1[k];
}
 
// Driver code
public static void Main(string[] args)
{
     
    // Given Strings
    string S = "ab", T = "ab";
 
    // Given K shifts required
    int K = 2;
 
    // Function call
    Console.Write(countWays(S, T, K));
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// JavaScript program for the above approach
 
let mod = 10000000007;
 
// Function to count number of ways to
// convert string S to string T by
// performing K cyclic shifts
function countWays(s, t, k)
{
     
    // Calculate length of string
    let n = s.length;
 
    // 'a' is no of good cyclic shifts
    // 'b' is no of bad cyclic shifts
    let a = 0, b = 0;
 
    // Iterate in the string
    for(let i = 0; i < n; i++)
    {
    let p = s.substr(i, n - i) +
                s.substr(0, i);
         
    // Precompute the number of good
    // and bad cyclic shifts
    if (p == t)
        a++;
    else
        b++;
    }
 
    // Initialize two dp arrays
    // dp1[i] to store the no of ways to
    // get to a good shift in i moves
 
    // dp2[i] to store the no of ways to
    // get to a bad shift in i moves
    let dp1 = Array.from({length: k+1}, (_, i) => 0);
    let dp2 = Array.from({length: k+1}, (_, i) => 0);
 
    if (s == t)
    {
        dp1[0] = 1;
        dp2[0] = 0;
    }
    else
    {
        dp1[0] = 0;
        dp2[0] = 1;
    }
 
    // Calculate good and bad shifts
    for(let i = 1; i <= k; i++)
    {
    dp1[i] = ((dp1[i - 1] * (a - 1)) % mod +
                (dp2[i - 1] * a) % mod) % mod;
    dp2[i] = ((dp1[i - 1] * (b)) % mod +
                (dp2[i - 1] * (b - 1)) % mod) % mod;
    }
 
    // Return the required number of ways
    return dp1[k];
}
 
// Driver Code
 
    // Given Strings
    let S = "ab", T = "ab";
 
    // Given K shifts required
    let K = 2;
 
    // Function Call
    document.write(countWays(S, T, K));
 
</script>
Producción: 

1

 

Complejidad temporal: O(N)  
Espacio auxiliar: O(K)
 

Publicación traducida automáticamente

Artículo escrito por rohitpal210 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 *