Consultas para verificar si la string B existe como substring en la string A

Dadas dos strings A , B y algunas consultas que consisten en un número entero i , la tarea es verificar si la substring de A que comienza en el índice i y termina en el índice i + longitud (B) – 1 es igual a B o no. Si es igual, imprima ; de lo contrario, imprima No. Tenga en cuenta que i + length(B) siempre será menor que length(A) .

Ejemplos: 

Entrada: A = “abababa”, B = “aba”, q[] = {0, 1, 2, 3} 
Salida: 
Si 
No 
Si 
No 
a[0-2] = “aba” = b (ambos son iguales) 
a[1-3] = “bab” != b 
a[2-4] = “aba” = b 
a[3-5] = “bab” !=b

Entrada: A = «GeeksForGeeks», B = «Geeks», q[] = {0, 5, 8} 
Salida: 
Sí 
No 
Sí  

Un enfoque simple será comparar las strings carácter por carácter para cada consulta, lo que llevará O (longitud (B)) tiempo para responder a cada consulta.

Enfoque eficiente: optimizaremos el procesamiento de consultas mediante el algoritmo  hash rodante .
Primero, encontraremos el valor hash de la string B. Luego, utilizando la técnica de hash rodante, haremos el preprocesamiento de la string A. 
Supongamos que creamos una array hash_A. Luego se almacenará el elemento i-ésimo de esta array. 

((a[0] – 97) + (a[1] – 97) * d + (a[2] – 97) * d 2 + ….. + (a[i] – 97) * d i ) % mod 
donde d es el multiplicador en rolling-hash. 

Usaremos esto para encontrar el hash de la substring de A. 

El hash de la substring de A a partir de i se puede encontrar como (hash_a[i + len_b – 1] – hash_a[i – 1]) / d i o más específicamente 

((hash_a[i + len_b – 1] – hash_a[i – 1] + 2 * mod) * mi(d i )) % mod 

Por lo tanto, usando esto podemos responder cada consulta en O(1).

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
#define mod 3803
#define d 26
using namespace std;
 
int hash_b;
int* hash_a;
int* mul;
 
// Function to return the modular inverse
// using Fermat's little theorem
int mi(int x)
{
    int p = mod - 2;
    int s = 1;
    while (p != 1) {
        if (p % 2 == 1)
            s = (s * x) % mod;
        x = (x * x) % mod;
        p /= 2;
    }
 
    return (s * x) % mod;
}
 
// Function to generate hash
void genHash(string& a, string& b)
{
    // To store prefix-sum
    // of rolling hash
    hash_a = new int[a.size()];
 
    // Multiplier for different values of i
    mul = new int[a.size()];
 
    // Generating hash value for string b
    for (int i = b.size() - 1; i >= 0; i--)
        hash_b = (hash_b * d + (b[i] - 97)) % mod;
 
    // Generating prefix-sum of hash of a
    mul[0] = 1;
    hash_a[0] = (a[0] - 97) % mod;
    for (int i = 1; i < a.size(); i++) {
        mul[i] = (mul[i - 1] * d) % mod;
        hash_a[i]
            = (hash_a[i - 1] + mul[i] * (a[i] - 97)) % mod;
    }
}
 
// Function that returns true if the
// required sub-string in a is equal to b
bool checkEqual(int i, int len_a, int len_b)
{
    // To store hash of required
    // sub-string of A
    int x;
 
    // If i = 0 then
    // requires hash value
    if (i == 0)
        x = hash_a[len_b - 1];
 
    // Required hash if i != 0
    else {
        x = (hash_a[i + len_b - 1] - hash_a[i - 1]
             + 2 * mod)
            % mod;
        x = (x * mi(mul[i])) % mod;
    }
 
    // Comparing hash with hash of B
    if (x == hash_b)
        return true;
 
    return false;
}
 
// Driver code
int main()
{
    string a = "abababababa";
    string b = "aba";
 
    // Generating hash
    genHash(a, b);
 
    // Queries
    int queries[] = { 0, 1, 2, 3 };
    int q = sizeof(queries) / sizeof(queries[0]);
 
    // Perform queries
    for (int i = 0; i < q; i++) {
        if (checkEqual(queries[i], a.size(), b.size()))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG {
 
    static int mod = 3803;
    static int d = 26;
 
    static int hash_b;
    static int[] hash_a;
    static int[] mul;
 
    // Function to return the modular inverse
    // using Fermat's little theorem
    static int mi(int x)
    {
        int p = mod - 2;
        int s = 1;
        while (p != 1) {
            if (p % 2 == 1) {
                s = (s * x) % mod;
            }
            x = (x * x) % mod;
            p /= 2;
        }
 
        return (s * x) % mod;
    }
 
    // Function to generate hash
    static void genHash(char[] a, char[] b)
    {
        // To store prefix-sum
        // of rolling hash
        hash_a = new int[a.length];
 
        // Multiplier for different values of i
        mul = new int[a.length];
 
        // Generating hash value for string b
        for (int i = b.length - 1; i >= 0; i--) {
            hash_b = (hash_b * d + (b[i] - 97)) % mod;
        }
 
        // Generating prefix-sum of hash of a
        mul[0] = 1;
        hash_a[0] = (a[0] - 97) % mod;
        for (int i = 1; i < a.length; i++) {
            mul[i] = (mul[i - 1] * d) % mod;
            hash_a[i]
                = (hash_a[i - 1] + mul[i] * (a[i] - 97))
                  % mod;
        }
    }
 
    // Function that returns true if the
    // required sub-string in a is equal to b
    static boolean checkEqual(int i, int len_a, int len_b)
    {
        // To store hash of required
        // sub-string of A
        int x;
 
        // If i = 0 then
        // requires hash value
        if (i == 0) {
            x = hash_a[len_b - 1];
        }
        // Required hash if i != 0
        else {
            x = (hash_a[i + len_b - 1] - hash_a[i - 1]
                 + 2 * mod)
                % mod;
            x = (x * mi(mul[i])) % mod;
        }
 
        // Comparing hash with hash of B
        if (x == hash_b) {
            return true;
        }
 
        return false;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String a = "abababababa";
        String b = "aba";
 
        // Generating hash
        genHash(a.toCharArray(), b.toCharArray());
 
        // Queries
        int queries[] = { 0, 1, 2, 3 };
        int q = queries.length;
 
        // Perform queries
        for (int i = 0; i < q; i++) {
            if (checkEqual(queries[i], a.length(),
                           b.length())) {
                System.out.println("Yes");
            }
            else {
                System.out.println("No");
            }
        }
    }
}
 
/* This code is contributed by PrinciRaj1992 */

Python3

# Python3 implementation of the approach
mod = 3803
d = 26
 
hash_b = 0
hash_a = []
mul = []
 
# Function to return the modular inverse
# using Fermat's little theorem
 
 
def mi(x):
    global mod
    p = mod - 2
    s = 1
    while p != 1:
        if p % 2 == 1:
            s = (s * x) % mod
 
        x = (x * x) % mod
        p //= 2
 
    return (s * x) % mod
 
# Function to generate hash
 
 
def genHash(a, b):
    global hash_b, hash_a, mul, d, mod
 
    # To store prefix-sum
    # of rolling hash
    hash_a = [0] * len(a)
 
    # Multiplier for different values of i
    mul = [0] * len(a)
 
    # Generating hash value for string b
    for i in range(len(b) - 1, -1, -1):
        hash_b = (hash_b * d +
                  (ord(b[i]) - 97)) % mod
 
    # Generating prefix-sum of hash of a
    mul[0] = 1
    hash_a[0] = (ord(a[0]) - 97) % mod
    for i in range(1, len(a)):
        mul[i] = (mul[i - 1] * d) % mod
        hash_a[i] = (hash_a[i - 1] + mul[i] *
                     (ord(a[i]) - 97)) % mod
 
# Function that returns true if the
# required sub-string in a is equal to b
 
 
def checkEqual(i, len_a, len_b):
    global hash_b, hash_a, mul, d, mod
 
    # To store hash of required
    # sub-string of A
    x = -1
 
    # If i = 0 then
    # requires hash value
    if i == 0:
        x = hash_a[len_b - 1]
 
    # Required hash if i != 0
    else:
        x = (hash_a[i + len_b - 1] -
             hash_a[i - 1] + 2 * mod) % mod
        x = (x * mi(mul[i])) % mod
 
    # Comparing hash with hash of B
    if x == hash_b:
        return True
 
    return False
 
 
# Driver Code
if __name__ == "__main__":
    a = "abababababa"
    b = "aba"
 
    # Generating hash
    genHash(a, b)
 
    # Queries
    queries = [0, 1, 2, 3]
    q = len(queries)
 
    # Perform queries
    for i in range(q):
        if checkEqual(queries[i], len(a), len(b)):
            print("Yes")
        else:
            print("No")
 
# This code is contributed by
# sanjeev2552

C#

// C# implementation of the approach
using System;
 
class GFG {
 
    static int mod = 3803;
    static int d = 26;
 
    static int hash_b;
    static int[] hash_a;
    static int[] mul;
 
    // Function to return the modular inverse
    // using Fermat's little theorem
    static int mi(int x)
    {
        int p = mod - 2;
        int s = 1;
        while (p != 1) {
            if (p % 2 == 1) {
                s = (s * x) % mod;
            }
            x = (x * x) % mod;
            p /= 2;
        }
 
        return (s * x) % mod;
    }
 
    // Function to generate hash
    static void genHash(char[] a, char[] b)
    {
        // To store prefix-sum
        // of rolling hash
        hash_a = new int[a.Length];
 
        // Multiplier for different values of i
        mul = new int[a.Length];
 
        // Generating hash value for string b
        for (int i = b.Length - 1; i >= 0; i--) {
            hash_b = (hash_b * d + (b[i] - 97)) % mod;
        }
 
        // Generating prefix-sum of hash of a
        mul[0] = 1;
        hash_a[0] = (a[0] - 97) % mod;
        for (int i = 1; i < a.Length; i++) {
            mul[i] = (mul[i - 1] * d) % mod;
            hash_a[i]
                = (hash_a[i - 1] + mul[i] * (a[i] - 97))
                  % mod;
        }
    }
 
    // Function that returns true if the
    // required sub-string in a is equal to b
    static Boolean checkEqual(int i, int len_a, int len_b)
    {
        // To store hash of required
        // sub-string of A
        int x;
 
        // If i = 0 then
        // requires hash value
        if (i == 0) {
            x = hash_a[len_b - 1];
        }
        // Required hash if i != 0
        else {
            x = (hash_a[i + len_b - 1] - hash_a[i - 1]
                 + 2 * mod)
                % mod;
            x = (x * mi(mul[i])) % mod;
        }
 
        // Comparing hash with hash of B
        if (x == hash_b) {
            return true;
        }
 
        return false;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String a = "abababababa";
        String b = "aba";
 
        // Generating hash
        genHash(a.ToCharArray(), b.ToCharArray());
 
        // Queries
        int[] queries = { 0, 1, 2, 3 };
        int q = queries.Length;
 
        // Perform queries
        for (int i = 0; i < q; i++) {
            if (checkEqual(queries[i], a.Length,
                           b.Length)) {
                Console.WriteLine("Yes");
            }
            else {
                Console.WriteLine("No");
            }
        }
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
// Javascript implementation of the approach
var mod = 3803;
var d = 26;
 
var hash_b = 0;
var hash_a = [];
var mul = [];
 
// Function to return the modular inverse
// using Fermat's little theorem
function mi(x)
{
    var p = mod - 2;
    var s = 1;
    while (p != 1) {
        if (p % 2 == 1)
            s = (s * x) % mod;
        x = (x * x) % mod;
        p = parseInt(p/2);
    }
 
    return (s * x) % mod;
}
 
// Function to generate hash
function genHash(a, b)
{
    // To store prefix-sum
    // of rolling hash
    hash_a = Array(a.length).fill(0);
 
    // Multiplier for different values of i
    mul = Array(a.length).fill(0);
 
    // Generating hash value for string b
    for (var i = b.length - 1; i >= 0; i--)
        hash_b = (hash_b * d + (b[i].charCodeAt(0) - 97)) % mod;
 
    // Generating prefix-sum of hash of a
    mul[0] = 1;
    hash_a[0] = (a[0].charCodeAt(0) - 97) % mod;
    for (var i = 1; i < a.length; i++) {
        mul[i] = (mul[i - 1] * d) % mod;
        hash_a[i]
            = (hash_a[i - 1] + mul[i] * (a[i].charCodeAt(0) - 97)) % mod;
    }
}
 
// Function that returns true if the
// required sub-string in a is equal to b
function checkEqual(i, len_a, len_b)
{
    // To store hash of required
    // sub-string of A
    var x;
 
    // If i = 0 then
    // requires hash value
    if (i == 0)
        x = hash_a[len_b - 1];
 
    // Required hash if i != 0
    else {
        x = (hash_a[i + len_b - 1] - hash_a[i - 1]
             + 2 * mod)
            % mod;
        x = (x * mi(mul[i])) % mod;
    }
 
    // Comparing hash with hash of B
    if (x == hash_b)
        return true;
 
    return false;
}
 
// Driver code
var a = "abababababa";
var b = "aba";
 
// Generating hash
genHash(a.split(''), b.split(''));
 
// Queries
var queries = [0, 1, 2, 3];
var q = queries.length
 
// Perform queries
for (var i = 0; i < q; i++) {
    if (checkEqual(queries[i], a.length, b.length))
        document.write("Yes<br>");
    else
    document.write("No<br>");
}
 
// This code is contributed by rrrtnx.
</script>
Producción

Yes
No
Yes
No

Nota: Para simplificar, hemos utilizado solo una función hash. Use hash doble/triple para eliminar cualquier posibilidad de colisión y obtener un resultado más preciso.

La pregunta anterior también se puede resolver usando DP, a continuación se muestra el código Java.

Java

import java.io.*;
import java.util.*;
import java.lang.*;
import java.io.*;
 
public class GFG
{
    private static void
    substringCheck(String stra, String strb, int[] query)
    {
 
        // Dp Array
        int[][] matrix
            = new int[strb.length()][stra.length()];
       
        // String to character array
        char[] charCrr = stra.toCharArray();
        char[] charRrr = strb.toCharArray();
 
        // initialize matrix with 1
        for (int c = 0; c < stra.length(); c++)
        {
            if (charRrr[0] == charCrr)
            {
                matrix[0] = 1;
            }
        }
 
        // for r from 1 to string length
        for (int r = 1; r < charRrr.length; r++)
        {
            char ch = charRrr[r];
 
            // for c from 1 b string length
            for (int c = 1; c < charCrr.length; c++)
            {
                if (ch == charCrr
                    && matrix[r - 1] == 1)
                {
                    matrix[r] = 1;
                }
            }
        }
 
        // For every query
        for (int q : query)
        {
            int matLoc = (q + (strb.length() - 1));
            if (matLoc >= stra.length()) {
                System.out.println(false);
            }
            else
            {
                // print true
                if (matrix[strb.length() - 1][matLoc]
                    == 1)
                {
                    System.out.println(true);
                }
                else
                {
                    // print false
                    System.out.println(false);
                }
            }
        }
 
    }
   
    // Driver Code
    public static void main(String[] args)
    {
        String stra = "GeeksForGeeks";
        String strb = "Geeks";
        int[] query = { 0,5,8 };
        substringCheck(stra, strb, query);
    }
 
} // class
// Code contributed by Swapnil Gupta

C#

using System;
 
public class GFG {
    private static void
    substringCheck(string stra, string strb, int[] query)
    {
 
        // Dp Array
        int[, ] matrix = new int[strb.Length, stra.Length];
 
        // String to character array
        char[] charCrr = stra.ToCharArray();
        char[] charRrr = strb.ToCharArray();
 
        // initialize matrix with 1
        for (int c = 0; c < stra.Length; c++) {
            if (charRrr[0] == charCrr) {
                matrix[0, c] = 1;
            }
        }
 
        // for r from 1 to string length
        for (int r = 1; r < charRrr.Length; r++) {
            char ch = charRrr[r];
 
            // for c from 1 b string length
            for (int c = 1; c < charCrr.Length; c++) {
                if (ch == charCrr
                    && matrix[r - 1, c - 1] == 1) {
                    matrix[r, c] = 1;
                }
            }
        }
 
        // For every query
        foreach(int q in query)
        {
            int matLoc = (q + (strb.Length - 1));
            if (matLoc >= stra.Length) {
                Console.WriteLine(false);
            }
            else {
                // print true
                if (matrix[strb.Length - 1, matLoc] == 1) {
                    Console.WriteLine(true);
                }
                else {
                    // print false
                    Console.WriteLine(false);
                }
            }
        }
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        string stra = "GeeksForGeeks";
        string strb = "Geeks";
        int[] query = { 0, 5, 8 };
        substringCheck(stra, strb, query);
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
function substringCheck(stra, strb, query)
{
    // Dp Array
    var matrix = Array.from(Array(strb.length), ()=>Array(stra.length));
   
    // String to character array
    var charCrr = stra.split('');
    var charRrr = strb.split('');
    // initialize matrix with 1
    for (var c = 0; c < stra.length; c++)
    {
        if (charRrr[0] == charCrr)
        {
            matrix[0] = 1;
        }
    }
    // for r from 1 to string length
    for (var r = 1; r < charRrr.length; r++)
    {
        var ch = charRrr[r];
        // for c from 1 b string length
        for (var c = 1; c < charCrr.length; c++)
        {
            if (ch == charCrr
                && matrix[r - 1] == 1)
            {
                matrix[r] = 1;
            }
        }
    }
    // For every query
    for (var q of query)
    {
        var matLoc = (q + (strb.length - 1));
        if (matLoc >= stra.length) {
            document.write(false + "<br>");
        }
        else
        {
            // print true
            if (matrix[strb.length - 1][matLoc]
                == 1)
            {
                document.write(true+ "<br>");
            }
            else
            {
                // print false
                document.write(false+ "<br>");
            }
        }
    }
}
 
// Driver Code
var stra = "GeeksForGeeks";
var strb = "Geeks";
var query = [0,5,8];
substringCheck(stra, strb, query);
 
// This code is contributed by rutvik_56.
</script>
Producción

true
false
true

Complejidad de tiempo: O(M*N)

Publicación traducida automáticamente

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