Número mínimo de veces que debe repetirse A de modo que B sea una substring de él

Dadas dos strings A y B . La tarea es encontrar el número mínimo de veces que debe repetirse A de modo que B sea una substring de ella. Si no existe tal solución, imprima -1 .

Ejemplos: 

Entrada: A = “abcd”, B = “cdabcdab” 
Salida: 3 
Repitiendo A tres veces (“abcdabcdabcd”), B es una substring de la misma. B no es una substring de A cuando se repite menos de 3 veces.

Entrada: A = “ab”, B = “cabina” 
Salida: -1 

Enfoque: 
imagine que escribimos S = A+A+A+… Si B es una substring de S , solo necesitamos verificar si algún índice es 0 o 1 o …. length(A) -1 comienza con B , ya que S es lo suficientemente largo para contener B , y S tiene un período de length(A) .
Ahora, supongamos que ans es el número mínimo para el cual length(B) <= length(A * ans) . Solo necesitamos verificar si B es una substring de A * ans o A * (ans+1) . Si intentamos k < ans , entonces B tiene una longitud mayor queUn * ans y por lo tanto no puede ser una substring. Cuando k = ans+1 , A * k ya es lo suficientemente grande como para probar todas las posiciones para B ( A[i:i+length(B)] == B for i = 0, 1, …, length(A) – 1 ).

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

// CPP program to find Minimum number of times A
// has to be repeated such that B is a substring of it
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a number
// is a substring of other or not
bool issubstring(string str2, string rep1)
{
    int M = str2.length();
    int N = rep1.length();
 
    // Check for substring from starting
    // from i'th index of main string
    for (int i = 0; i <= N - M; i++) {
        int j;
 
        // For current index i,
        // check for pattern match
        for (j = 0; j < M; j++)
            if (rep1[i + j] != str2[j])
                break;
 
        if (j == M) // pattern matched
            return true;
    }
 
    return false; // not a substring
}
 
// Function to find Minimum number of times A
// has to be repeated such that B is a substring of it
int Min_repetation(string A, string B)
{
    // To store minimum number of repetitions
    int ans = 1;
     
    // To store repeated string
    string S = A;
     
    // Until size of S is less than B
    while(S.size() < B.size())
    {
        S += A;
        ans++;
    }
     
    // ans times repetition makes required answer
    if (issubstring(B, S)) return ans;
     
    // Add one more string of A  
    if (issubstring(B, S+A))
        return ans + 1;
         
    // If no such solution exists   
    return -1;
}
 
// Driver code
int main()
{
    string A = "abcd", B = "cdabcdab";
     
    // Function call
    cout << Min_repetation(A, B);
     
    return 0;
}

// Java program to find minimum number
// of times 'A' has to be repeated
// such that 'B' is a substring of it
class GFG
{
 
// Function to check if a number
// is a substring of other or not
static boolean issubstring(String str2,
                           String rep1)
{
    int M = str2.length();
    int N = rep1.length();
 
    // Check for substring from starting
    // from i'th index of main string
    for (int i = 0; i <= N - M; i++)
    {
        int j;
 
        // For current index i,
        // check for pattern match
        for (j = 0; j < M; j++)
            if (rep1.charAt(i + j) != str2.charAt(j))
                break;
 
        if (j == M) // pattern matched
            return true;
    }
 
    return false; // not a substring
}
 
// Function to find Minimum number
// of times 'A' has to be repeated
// such that 'B' is a substring of it
static int Min_repetation(String A, String B)
{
    // To store minimum number of repetitions
    int ans = 1;
     
    // To store repeated string
    String S = A;
     
    // Until size of S is less than B
    while(S.length() < B.length())
    {
        S += A;
        ans++;
    }
     
    // ans times repetition makes required answer
    if (issubstring(B, S)) return ans;
     
    // Add one more string of A
    if (issubstring(B, S + A))
        return ans + 1;
         
    // If no such solution exists
    return -1;
}
 
// Driver code
public static void main(String[] args)
{
    String A = "abcd", B = "cdabcdab";
     
    // Function call
    System.out.println(Min_repetation(A, B));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to find minimum number
# of times 'A' has to be repeated
# such that 'B' is a substring of it
 
# Method to find Minimum number
# of times 'A' has to be repeated
# such that 'B' is a substring of it
def min_repetitions(a, b):
    len_a = len(a)
    len_b = len(b)
     
    for i in range(0, len_a):
         
        if a[i] == b[0]:
            k = i
            count = 1
            for j in range(0, len_b):
                 
                # we are reiterating over A again and
                # again for each value of B
                # Resetting A pointer back to 0 as B
                # is not empty yet
                if k >= len_a:
                    k = 0
                    count = count + 1
                     
                # Resetting A means count
                # needs to be increased
                if a[k] != b[j]:
                    break
                k = k + 1
                 
            # k is iterating over A
            else:
                return count
    return -1
 
# Driver Code
A = 'abcd'
B = 'cdabcdab'
print(min_repetitions(A, B))
 
# This code is contributed by satycool

// C# program to find minimum number
// of times 'A' has to be repeated
// such that 'B' is a substring of it
using System;
     
class GFG
{
 
// Function to check if a number
// is a substring of other or not
static Boolean issubstring(String str2,
                           String rep1)
{
    int M = str2.Length;
    int N = rep1.Length;
 
    // Check for substring from starting
    // from i'th index of main string
    for (int i = 0; i <= N - M; i++)
    {
        int j;
 
        // For current index i,
        // check for pattern match
        for (j = 0; j < M; j++)
            if (rep1[i + j] != str2[j])
                break;
 
        if (j == M) // pattern matched
            return true;
    }
 
    return false; // not a substring
}
 
// Function to find Minimum number
// of times 'A' has to be repeated
// such that 'B' is a substring of it
static int Min_repetation(String A, String B)
{
    // To store minimum number of repetitions
    int ans = 1;
     
    // To store repeated string
    String S = A;
     
    // Until size of S is less than B
    while(S.Length < B.Length)
    {
        S += A;
        ans++;
    }
     
    // ans times repetition makes required answer
    if (issubstring(B, S)) return ans;
     
    // Add one more string of A
    if (issubstring(B, S + A))
        return ans + 1;
         
    // If no such solution exists
    return -1;
}
 
// Driver code
public static void Main(String[] args)
{
    String A = "abcd", B = "cdabcdab";
     
    // Function call
    Console.WriteLine(Min_repetation(A, B));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to find Minimum number of times A
// has to be repeated such that B is a substring of it
 
// Function to check if a number
// is a substring of other or not
function issubstring(str2, rep1)
{
    var M = str2.length;
    var N = rep1.length;
 
    // Check for substring from starting
    // from i'th index of main string
    for (var i = 0; i <= N - M; i++) {
        var j;
 
        // For current index i,
        // check for pattern match
        for (j = 0; j < M; j++)
            if (rep1[i + j] != str2[j])
                break;
 
        if (j == M) // pattern matched
            return true;
    }
 
    return false; // not a substring
}
 
// Function to find Minimum number of times A
// has to be repeated such that B is a substring of it
function Min_repetation(A, B)
{
    // To store minimum number of repetitions
    var ans = 1;
     
    // To store repeated string
    var S = A;
     
    // Until size of S is less than B
    while(S.length < B.length)
    {
        S += A;
        ans++;
    }
     
    // ans times repetition makes required answer
    if (issubstring(B, S))
        return ans;
     
    // Add one more string of A  
    if (issubstring(B, S+A))
        return ans + 1;
         
    // If no such solution exists   
    return -1;
}
 
// Driver code
var A = "abcd", B = "cdabcdab";
 
// Function call
document.write( Min_repetation(A, B));
 
 
</script>

3

Complejidad Temporal: O(N * M) 
Espacio Auxiliar : O(1).  

Enfoque 2:

La idea aquí es tratar de encontrar la string usando un algoritmo de búsqueda de string de fuerza bruta (n * m). La única diferencia aquí es calcular el módulo (i % n) cuando el contador llega al final de la string.

#include <bits/stdc++.h>
using namespace std;
 
int repeatedStringMatch(string A, string B)
{
    int m = A.length();
    int n = B.length();
 
    int count;
    bool found = false;
 
    for (int i = 0; i < m; i++) {
        int j = i;
        int k = 0;
        count = 1;
 
        while (k < n && A[j] == B[k]) {
            if (k == n - 1) {
                found = true;
                break;
            }
            j = (j + 1) % m;
 
            if (j == 0)
                count++;
 
            k++;
        }
        if (found)
            return count;
    }
    return -1;
}
int main()
{
    string A = "abcd";
    string B = "cdabcdab";
 
    cout << repeatedStringMatch(A, B);
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    static int repeatedStringMatch(String A, String B)
    {
        int m = A.length();
        int n = B.length();
 
        int count;
        boolean found = false;
 
        for (int i = 0; i < m; ++i) {
            int j = i;
 
            int k = 0;
 
            count = 1;
 
            while (k < n && A.charAt(j) == B.charAt(k)) {
 
                if (k == n - 1) {
                    found = true;
                    break;
                }
 
                j = (j + 1) % m;
 
                // if j = 0, it means we have repeated the
                // string
                if (j == 0)
                    ++count;
 
                k += 1;
            }
 
            if (found)
                return count;
        }
 
        return -1;
    }
    public static void main(String[] args)
    {
 
        String A = "abcd", B = "cdabcdab";
 
        // Function call
        System.out.println(repeatedStringMatch(A, B));
    }
}

# Python implementation of this approach
def repeatedStringMatch(A, B):
 
    m = len(A)
    n = len(B)
 
    count = 0
    found = False
 
    for i in range(m):
        j = i
        k = 0
        count = 1
 
        while k < n and A[j] == B[k] :
            if (k == n - 1) :
                found = True
                break
             
            j = (j + 1) % m
 
            if (j == 0):
                count = count + 1
 
            k = k + 1
         
        if (found):
            return count
    return -1
 
# Driver code
A = "abcd";
B = "cdabcdab";
 
print(repeatedStringMatch(A, B));
 
# This code is contributed by shinjanpatra

// C# program to find minimum number
// of times 'A' has to be repeated
// such that 'B' is a substring of it
using System;
     
class GFG
{
static int repeatedStringMatch(string A, string B)
{
    int m = A.Length;
    int n = B.Length;
  
    int count;
    bool found = false;
  
    for (int i = 0; i < m; i++) {
        int j = i;
        int k = 0;
        count = 1;
  
        while (k < n && A[j] == B[k]) {
            if (k == n - 1) {
                found = true;
                break;
            }
            j = (j + 1) % m;
  
            if (j == 0)
                count++;
  
            k++;
        }
        if (found)
            return count;
    }
    return -1;
}
 
 
// Driver code
public static void Main(String[] args)
{
    String A = "abcd", B = "cdabcdab";
     
    // Function call
    Console.WriteLine(repeatedStringMatch(A, B));
}
}
 
// This code is contributed by Pushpesh Raj

<script>
 
// JavaScript implementation of this approach
 
function repeatedStringMatch(A, B)
{
    let m = A.length;
    let n = B.length;
 
    let count;
    let found = false;
 
    for (let i = 0; i < m; i++) {
        let j = i;
        let k = 0;
        count = 1;
 
        while (k < n && A[j] == B[k]) {
            if (k == n - 1) {
                found = true;
                break;
            }
            j = (j + 1) % m;
 
            if (j == 0)
                count++;
 
            k++;
        }
        if (found)
            return count;
    }
    return -1;
}
 
// Driver code
let A = "abcd";
let B = "cdabcdab";
document.write(repeatedStringMatch(A, B));
 
</script>
 
// This code is contributed by shinjanpatra

 Complejidad de tiempo: O(N * M) 

Espacio Auxiliar: O(1).