Recuento de strings distintas posible insertando K caracteres en la string original

Posted on by Rudeus Greyrat

Dada una string S y un entero K , la tarea es encontrar el número total de strings que se pueden formar insertando exactamente K caracteres en cualquier posición de la string S. Como la respuesta puede ser grande, imprímela módulo 10 9 +7 .
Ejemplos:

Entrada: S = “a” K = 1 
Salida: 51 
Explicación: 
Dado que cualquiera de los 26 caracteres se puede insertar antes de ‘a’ o después de ‘a’, se pueden formar un total de 52 strings posibles. 
Pero la string «aa» se forma dos veces. Por lo tanto, el número de strings distintas posibles es 51.
Entrada: S = «abc» K = 2 
Salida: 6376

Enfoque: 
La idea es encontrar el número de strings que contiene la str como una subsecuencia. Siga los pasos a continuación para resolver el problema:

  1. El número total de strings que pueden estar formadas por N caracteres es 26 N .
  2. Calcule 26 N usando Exponenciación Binaria .
  3. En este problema, solo se deben considerar las strings que contienen str como una subsecuencia .
  4. Por lo tanto, el conteo final de strings viene dado por

 
 

(número total de strings) – (número de strings que no contienen la string de entrada como una subsecuencia)

 

  1. Al calcular las strings que no contienen str como una subsecuencia, observe que la longitud del prefijo de S es una subsecuencia de la string resultante que puede estar entre 0 y |S|-1 .
  2. Para cada longitud de prefijo de 0 a |S|-1 , encuentre el número total de strings que se pueden formar con dicho prefijo como una subsecuencia. Luego reste ese valor de 26 N .
  3. Por lo tanto, la respuesta final es:

26^{N} - \sum_{i = 0}^{|S| - 1} \binom{N}{i}*25^{N - i}

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 int long long int
const int mod = 1e9 + 7;
 
// Function to calculate and return
// x^n in log(n) time using
// Binary Exponentiation
int binExp(int base, int power)
{
    int x = 1;
    while (power) {
        if (power % 2 == 1)
            x = ((x % mod)
                 * (base % mod))
                % mod;
 
        base = ((base % mod)
                * (base % mod))
               % mod;
        power = power / 2;
    }
    return x;
}
 
// Function to calculate the factorial
// of a number
int fact(int num)
{
    int result = 1;
 
    for (int i = 1; i <= num; ++i) {
 
        result = ((result % mod)
                  * (i % mod))
                 % mod;
    }
 
    return result;
}
 
// Function to calculate combination
int calculate_nCi(int N, int i)
{
    // nCi = ( n! ) / (( n-i )! * i!)
    int nfact = fact(N);
    int ifact = fact(i);
    int dfact = fact(N - i);
 
    // Using Euler's theorem of Modular
    // multiplicative inverse to find
    // the inverse of a number.
    // (1/a)%mod=a^(m?2)%mod
    int inv_ifact = binExp(ifact, mod - 2);
    int inv_dfact = binExp(dfact, mod - 2);
 
    int denm
        = ((inv_ifact % mod)
           * (inv_dfact % mod))
          % mod;
 
    int answer = ((nfact % mod)
                  * (denm % mod))
                 % mod;
    return answer;
}
 
// Function to find the count of
// possible strings
void countSubstring(int N, int s, int k)
{
    // Number of ways to form all
    // possible strings
    int allWays = binExp(26, N);
 
    // Number of ways to form strings
    // that don't contain the input
    // string as a subsequence
    int noWays = 0;
 
    // Checking for all prefix length
    // from 0 to |S|-1.
    for (int i = 0; i < s; ++i) {
        // to calculate nCi
        int nCi = calculate_nCi(N, i);
 
        // Select the remaining characters
        // 25 ^ (N-i)
        int remaining = binExp(25, N - i);
 
        int multiply
            = ((nCi % mod)
               * (remaining % mod))
              % mod;
 
        // Add the answer for this prefix
        // length to the final answer
        noWays = ((noWays % mod)
                  + (multiply % mod))
                 % mod;
    }
 
    // Answer is the difference of
    // allWays and noWays
    int answer = ((allWays % mod)
                  - (noWays % mod))
                 % mod;
 
    if (answer < 0)
        answer += mod;
 
    // Print the answer
    cout << answer;
}
 
// Driver Code
int32_t main()
{
    string str = "abc";
    int k = 2;
    int s = str.length();
 
    int N = s + k;
 
    countSubstring(N, s, k);
}

Java

// Java program for the above approach
class GFG{
 
static final long mod = 1000000007;
 
// Function to calculate and return
// x^n in log(n) time using
// Binary Exponentiation
static long binExp(long base, long power)
{
    long x = 1;
    while (power != 0)
    {
        if (power % 2 == 1)
            x = ((x % mod) *
              (base % mod)) % mod;
 
        base = ((base % mod) *
                (base % mod)) % mod;
        power = power / 2;
    }
    return x;
}
 
// Function to calculate the factorial
// of a number
static long fact(long num)
{
    long result = 1;
 
    for(long i = 1; i <= num; ++i)
    {
        result = ((result % mod) *
                       (i % mod)) % mod;
    }
    return result;
}
 
// Function to calculate combination
static long calculate_nCi(long N, long i)
{
     
    // nCi = ( n! ) / (( n-i )! * i!)
    long nfact = fact(N);
    long ifact = fact(i);
    long dfact = fact(N - i);
 
    // Using Euler's theorem of Modular
    // multiplicative inverse to find
    // the inverse of a number.
    // (1/a)%mod=a^(m?2)%mod
    long inv_ifact = binExp(ifact, mod - 2);
    long inv_dfact = binExp(dfact, mod - 2);
 
    long denm = ((inv_ifact % mod) *
                 (inv_dfact % mod)) % mod;
 
    long answer = ((nfact % mod) *
                    (denm % mod)) % mod;
    return answer;
}
 
// Function to find the count of
// possible strings
static void countSubstring(long N, long s, long k)
{
     
    // Number of ways to form all
    // possible strings
    long allWays = binExp(26, N);
 
    // Number of ways to form strings
    // that don't contain the input
    // string as a subsequence
    long noWays = 0;
 
    // Checking for all prefix length
    // from 0 to |S|-1.
    for(long i = 0; i < s; ++i)
    {
         
        // To calculate nCi
        long nCi = calculate_nCi(N, i);
 
        // Select the remaining characters
        // 25 ^ (N-i)
        long remaining = binExp(25, N - i);
 
        long multiply = ((nCi % mod) *
                   (remaining % mod)) % mod;
 
        // Add the answer for this prefix
        // length to the final answer
        noWays = ((noWays % mod) +
                (multiply % mod)) % mod;
    }
 
    // Answer is the difference of
    // allWays and noWays
    long answer = ((allWays % mod) -
                    (noWays % mod)) % mod;
 
    if (answer < 0)
        answer += mod;
 
    // Print the answer
    System.out.println(answer);
}
     
// Driver code   
public static void main(String[] args)
{
    String str = "abc";
    long k = 2;
    long s = str.length();
    long N = s + k;
     
    countSubstring(N, s, k);
}
}
 
// This code is contributed by rutvik_56

Python3

# Python3 program for the above approach
mod = 1000000007
 
# Function to calculate and return
# x^n in log(n) time using
# Binary Exponentiation
def binExp(base, power):
 
    x = 1
    while (power):
        if (power % 2 == 1):
            x = (((x % mod) *
               (base % mod)) % mod)
 
        base = (((base % mod) *
                 (base % mod)) % mod)
        power = power // 2
     
    return x
 
# Function to calculate the factorial
# of a number
def fact(num):
 
    result = 1
 
    for i in range(1, num + 1):
        result = (((result % mod) *
                        (i % mod)) % mod)
                         
    return result
 
# Function to calculate combination
def calculate_nCi(N, i):
 
    # nCi = ( n! ) / (( n-i )! * i!)
    nfact = fact(N)
    ifact = fact(i)
    dfact = fact(N - i)
 
    # Using Euler's theorem of Modular
    # multiplicative inverse to find
    # the inverse of a number.
    # (1/a)%mod=a^(m?2)%mod
    inv_ifact = binExp(ifact, mod - 2)
    inv_dfact = binExp(dfact, mod - 2)
 
    denm = (((inv_ifact % mod) *
             (inv_dfact % mod)) % mod)
 
    answer = (((nfact % mod) *
                (denm % mod)) % mod)
                 
    return answer
 
# Function to find the count of
# possible strings
def countSubstring(N, s, k):
 
    # Number of ways to form all
    # possible strings
    allWays = binExp(26, N)
 
    # Number of ways to form strings
    # that don't contain the input
    # string as a subsequence
    noWays = 0
 
    # Checking for all prefix length
    # from 0 to |S|-1.
    for i in range(s):
         
        # To calculate nCi
        nCi = calculate_nCi(N, i)
 
        # Select the remaining characters
        # 25 ^ (N-i)
        remaining = binExp(25, N - i)
 
        multiply = (((nCi % mod) *
              (remaining % mod)) % mod)
 
        # Add the answer for this prefix
        # length to the final answer
        noWays =(((noWays % mod) +
                (multiply % mod)) % mod)
     
    # Answer is the difference of
    # allWays and noWays
    answer = (((allWays % mod) -
               (noWays % mod)) % mod)
 
    if (answer < 0):
        answer += mod
 
    # Print the answer
    print(answer)
 
# Driver Code
if __name__ == "__main__":
 
    st = "abc"
    k = 2
    s = len(st)
 
    N = s + k
 
    countSubstring(N, s, k)
 
# This code is contributed by chitranayal

C#

// C# program for the above approach
using System;
 
class GFG{
 
static readonly long mod = 1000000007;
 
// Function to calculate and return
// x^n in log(n) time using
// Binary Exponentiation
static long binExp(long Base, long power)
{
    long x = 1;
    while (power != 0)
    {
        if (power % 2 == 1)
            x = ((x % mod) *
              (Base % mod)) % mod;
 
        Base = ((Base % mod) *
                (Base % mod)) % mod;
        power = power / 2;
    }
    return x;
}
 
// Function to calculate the factorial
// of a number
static long fact(long num)
{
    long result = 1;
 
    for(long i = 1; i <= num; ++i)
    {
        result = ((result % mod) *
                       (i % mod)) % mod;
    }
    return result;
}
 
// Function to calculate combination
static long calculate_nCi(long N, long i)
{
    // nCi = ( n! ) / (( n-i )! * i!)
    long nfact = fact(N);
    long ifact = fact(i);
    long dfact = fact(N - i);
 
    // Using Euler's theorem of Modular
    // multiplicative inverse to find
    // the inverse of a number.
    // (1/a)%mod=a^(m?2)%mod
    long inv_ifact = binExp(ifact, mod - 2);
    long inv_dfact = binExp(dfact, mod - 2);
 
    long denm = ((inv_ifact % mod) *
                 (inv_dfact % mod)) % mod;
 
    long answer = ((nfact % mod) *
                    (denm % mod)) % mod;
    return answer;
}
 
// Function to find the count of
// possible strings
static void countSubstring(long N, long s, long k)
{
     
    // Number of ways to form all
    // possible strings
    long allWays = binExp(26, N);
 
    // Number of ways to form strings
    // that don't contain the input
    // string as a subsequence
    long noWays = 0;
 
    // Checking for all prefix length
    // from 0 to |S|-1.
    for(long i = 0; i < s; ++i)
    {
         
        // To calculate nCi
        long nCi = calculate_nCi(N, i);
 
        // Select the remaining characters
        // 25 ^ (N-i)
        long remaining = binExp(25, N - i);
 
        long multiply = ((nCi % mod) *
                   (remaining % mod)) % mod;
 
        // Add the answer for this prefix
        // length to the readonly answer
        noWays = ((noWays % mod) +
                (multiply % mod)) % mod;
    }
 
    // Answer is the difference of
    // allWays and noWays
    long answer = ((allWays % mod) -
                    (noWays % mod)) % mod;
 
    if (answer < 0)
        answer += mod;
 
    // Print the answer
    Console.WriteLine(answer);
}
     
// Driver code
public static void Main(String[] args)
{
    String str = "abc";
    long k = 2;
    long s = str.Length;
    long N = s + k;
     
    countSubstring(N, s, k);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for the above approach   
 var mod = 10007;
 
    // Function to calculate and return
    // x^n in log(n) time using
    // Binary Exponentiation
    function binExp(base , power) {
        var x = 1;
        while (power != 0) {
            if (power % 2 == 1)
                x = (((x % mod) * (base % mod)) % mod);
 
            base = (((base % mod) * (base % mod)) % mod);
            power = parseInt(power / 2);
        }
        return x;
    }
 
    // Function to calculate the factorial
    // of a number
    function fact(num) {
        var result = 1;
 
        for (var i = 1; i <= num; ++i) {
            result = (((result % mod) * (i % mod)) % mod);
        }
        return result;
    }
 
    // Function to calculate combination
    function calculate_nCi(N , i) {
 
        // nCi = ( n! ) / (( n-i )! * i!)
        var nfact = fact(N);
        var ifact = fact(i);
        var dfact = fact(N - i);
 
        // Using Euler's theorem of Modular
        // multiplicative inverse to find
        // the inverse of a number.
        // (1/a)%mod=a^(m?2)%mod
        var inv_ifact = binExp(ifact, mod - 2);
        var inv_dfact = binExp(dfact, mod - 2);
 
        var denm = (((inv_ifact % mod) * (inv_dfact % mod)) % mod);
 
        var answer = (((nfact % mod) * (denm % mod)) % mod);
        return answer;
    }
 
    // Function to find the count of
    // possible strings
    function countSubstring(N , s , k) {
 
        // Number of ways to form all
        // possible strings
        var allWays = binExp(26, N);
 
        // Number of ways to form strings
        // that don't contain the input
        // string as a subsequence
        var noWays = 0;
 
        // Checking for all prefix length
        // from 0 to |S|-1.
        for (var i = 0; i < s; ++i) {
 
            // To calculate nCi
            var nCi = calculate_nCi(N, i);
 
            // Select the remaining characters
            // 25 ^ (N-i)
            var remaining = binExp(25, N - i);
 
            var multiply = (((nCi % mod) * (remaining % mod)) % mod);
 
            // Add the answer for this prefix
            // length to the final answer
            noWays = (((noWays % mod) + (multiply % mod)) % mod);
        }
 
        // Answer is the difference of
        // allWays and noWays
        var answer = (((allWays % mod) - (noWays % mod)) % mod);
 
        if (answer < 0)
            answer += mod;
 
        // Print the answer
        document.write(answer);
    }
 
    // Driver code
     
        var str = "abc";
        var k = 2;
        var s = str.length;
        var N = s + k;
 
        countSubstring(N, s, k);
 
// This code contributed by umadevi9616
 
</script>
Producción: 

6376

 

Complejidad de tiempo: O(N), donde N es la longitud de la string dada. 
Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

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