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 Sí ; 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” !=bEntrada: 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