Dada una string y varias consultas sobre las substrings de la string de entrada dada para verificar si la substring es un palíndromo o no.
Ejemplos:
Supongamos que nuestra string de entrada es «abaaabaaaba» y las consultas: [0, 10], [5, 8], [2, 5], [5, 9]
Tenemos que decir que la substring que tiene los índices de inicio y finalización como arriba es un palíndromo o no.
[0, 10] → La substring es “abaaabaaaba”, que es un palíndromo.
[5, 8] → La substring es “baaa”, que no es un palíndromo.
[2, 5] → La substring es “aaab”, que no es un palíndromo.
[5, 9] → La substring es “baaab”, que es un palíndromo.
Supongamos que hay Q consultas de este tipo para responder y que N es la longitud de nuestra string de entrada. Hay las siguientes dos formas de responder a estas consultas
Método 1 (ingenuo) :
Una por una, revisamos todas las substrings de las consultas y verificamos si la substring en consideración es un palíndromo o no.
Dado que hay consultas Q y cada consulta puede tardar O(N) en el peor de los casos para responder, este método tarda O(QN) en el peor de los casos. Aunque este es un algoritmo in situ/eficiente en el espacio, existe un método más eficiente para hacerlo.
Método 2 (hash acumulativo):
La idea es similar a la coincidencia de strings de Rabin Karp . Usamos hashing de strings. Lo que hacemos es calcular los valores hash acumulativos de la string en la string original, así como la string invertida en dos arrays: prefijo [] y sufijo [].
¿Cómo calcular los valores hash acumulativos?
Supongamos que nuestra string es str[], entonces la función hash acumulativa para llenar nuestra array de prefijos[] utilizada es-
prefijo[0] = 0
prefijo[i] = str[0] + str[1] * 101 + str[2] * 101 2 + …… + str[i-1] * 101 i-1
Por ejemplo, tome el string- “abaaabxyaba”
prefijo[0] = 0
prefijo[1] = 97 (El valor ASCII de ‘a’ es 97)
prefijo[2] = 97 + 98 * 101
prefijo[3] = 97 + 98 * 101 + 97 * 101 2
………………………
………………………
prefijo[11] = 97 + 98 * 101 + 97 * 101 2 + ……..+ 97 * 101 10
Ahora, la razón para almacenar de esa manera es que podemos encontrar fácilmente el valor hash de cualquier substring en tiempo O (1) usando-
hash(L, R) = prefix[R+1] – prefix[L]
Por ejemplo, hash (1, 5) = hash (“baaab”) = prefijo[6] – prefijo[1] = 98 * 101 + 97 * 101 2 + 97 * 101 3 + 97 * 101 4 + 98 * 101 5 = 1040184646587 [Usaremos este extraño valor más adelante para explicar lo que está pasando].
Similar a esto, llenaremos nuestra array sufijo [] como-
sufijo[0] = 0
sufijo[i] = str[n-1] + str[n-2] * 101 1 + str[n-3] * 101 2 + …… + str[ni] * 101 i-1
Por ejemplo, tome la string- “abaaabxyaba”
sufijo[0] = 0
sufijo[1] = 97 (el valor ASCII de ‘a’ es 97)
sufijo[2] = 97 + 98 * 101
sufijo[3] = 97 + 98 * 101 + 97 * 101 2
………………………
………………………
sufijo[11] = 97 + 98 * 101 + 97 * 101 2 + ……..+ 97 * 101 10
Ahora, la razón para almacenar de esa manera es que podemos encontrar fácilmente el valor hash inverso de cualquier substring en el tiempo O (1) usando
reverse_hash(L, R) = hash (R, L) = suffix[n-L] – suffix[n-R-1]donde n = longitud de la string.
Para “abaaabxyaba”, n = 11
reverse_hash(1, 5) = reverse_hash(“baaab”) = hash(“baaab”) [Invertir “baaab” da “baaab”]
hash(“baaab”) = sufijo[11-1 ] – sufijo[11-5-1] = sufijo[10] – sufijo[5] = 98 * 101 5 + 97 * 101 6 + 97 * 101 7 + 97 * 101 8 + 98 * 101 9 = 108242031437886501387
Ahora no parece haber ninguna relación entre estos dos enteros extraños: 1040184646587 y 108242031437886501387
Piénsalo de nuevo. ¿Existe alguna relación entre estos dos enteros masivos?
Sí, la hay y esta observación es el núcleo de este programa/artículo.
1040184646587 * 101 4 = 108242031437886501387
Intente pensar en esto y encontrará que cualquier substring que comience en índice-L y termine en índice-R (ambos inclusive) será un palíndromo si
(prefijo[R + 1] – prefijo[L]) / (101 L ) = (sufijo [n – L] – sufijo [n – R- 1] ) / (101 n – R – 1 )
El resto es solo implementación.
La función computerPowers() del programa calcula las potencias de 101 usando programación dinámica.Problemas de desbordamiento:
Como podemos ver, los valores hash y los valores hash inversos pueden volverse enormes incluso para las strings pequeñas de longitud: 8. Dado que C y C++ no brindan soporte para números tan grandes, causará desbordamientos. Para evitar esto, tomaremos el módulo de un primo (se elige un número primo por algunas razones matemáticas específicas). Elegimos el primo más grande posible que quepa en un valor entero. El mejor valor de este tipo es 1000000007. Por lo tanto, todas las operaciones se realizan en módulo 1000000007.
Sin embargo, Java y Python no tienen tales problemas y se pueden implementar sin el operador de módulo.
Las operaciones de módulo fundamentales que se utilizan ampliamente en el programa se enumeran a continuación.
1) Adición-
(a + b) %M = (a %M + b % M) % M
(a + b + c) % M = (a % M + b % M + c % M) % M
(a + b + c + d) % M = (a % M + b % M + c % M+ d% M) % M
…. ….. ….. ……
…. ….. ….. ……
2) Multiplicación-
(a * b) % M = (a * b) % M
(a * b * c) % M = ((a * b) % M * c % M) % M
(a * b * c * d) % M = ((((a * b) % M * c) % M) * d) % M
…. ….. ….. ……
…. ….. ….. ……Esta propiedad es utilizada por la función modPow() que calcula la potencia de un número módulo M
3) Mezcla de suma y multiplicación-
(a * x + b * y + c) % METRO = ( (a * x) % METRO +(b * y) % METRO+ c % METRO ) % METRO
4) Resta-
(a – b) % M = (a % M – b % M + M) % M [Correcto]
(a – b) % M = (a % M – b % M) % M [Incorrecto]
5) División-
(a / b) % M = (a * MMI(b)) % M
Donde MMI() es una función para calcular Modulo Multiplicativo Inverso. En nuestro programa esto se implementa mediante la función findMMI().
Implementación del enfoque anterior:
C++
/* A C++ program to answer queries to check whether
the substrings are palindrome or not efficiently */
#include <bits/stdc++.h>
using namespace std;
#define p 101
#define MOD 1000000007
// Structure to represent a query. A query consists
// of (L, R) and we have to answer whether the substring
// from index-L to R is a palindrome or not
struct Query {
int L, R;
};
// A function to check if a string str is palindrome
// in the range L to R
bool isPalindrome(string str, int L, int R)
{
// Keep comparing characters while they are same
while (R > L)
if (str[L++] != str[R--])
return (false);
return (true);
}
// A Function to find pow (base, exponent) % MOD
// in log (exponent) time
unsigned long long int modPow(
unsigned long long int base,
unsigned long long int exponent)
{
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
unsigned long long int temp = modPow(base, exponent / 2);
if (exponent % 2 == 0)
return (temp % MOD * temp % MOD) % MOD;
else
return (((temp % MOD * temp % MOD) % MOD)
* base % MOD)
% MOD;
}
// A Function to calculate Modulo Multiplicative Inverse of 'n'
unsigned long long int findMMI(unsigned long long int n)
{
return modPow(n, MOD - 2);
}
// A Function to calculate the prefix hash
void computePrefixHash(
string str, int n,
unsigned long long int prefix[],
unsigned long long int power[])
{
prefix[0] = 0;
prefix[1] = str[0];
for (int i = 2; i <= n; i++)
prefix[i] = (prefix[i - 1] % MOD
+ (str[i - 1] % MOD
* power[i - 1] % MOD)
% MOD)
% MOD;
return;
}
// A Function to calculate the suffix hash
// Suffix hash is nothing but the prefix hash of
// the reversed string
void computeSuffixHash(
string str, int n,
unsigned long long int suffix[],
unsigned long long int power[])
{
suffix[0] = 0;
suffix[1] = str[n - 1];
for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
suffix[j] = (suffix[j - 1] % MOD
+ (str[i] % MOD
* power[j - 1] % MOD)
% MOD)
% MOD;
return;
}
// A Function to answer the Queries
void queryResults(string str, Query q[], int m, int n,
unsigned long long int prefix[],
unsigned long long int suffix[],
unsigned long long int power[])
{
for (int i = 0; i <= m - 1; i++) {
int L = q[i].L;
int R = q[i].R;
// Hash Value of Substring [L, R]
unsigned long long hash_LR
= ((prefix[R + 1] - prefix[L] + MOD) % MOD
* findMMI(power[L]) % MOD)
% MOD;
// Reverse Hash Value of Substring [L, R]
unsigned long long reverse_hash_LR
= ((suffix[n - L] - suffix[n - R - 1] + MOD) % MOD
* findMMI(power[n - R - 1]) % MOD)
% MOD;
// If both are equal then
// the substring is a palindrome
if (hash_LR == reverse_hash_LR) {
if (isPalindrome(str, L, R) == true)
printf("The Substring [%d %d] is a "
"palindrome\n",
L, R);
else
printf("The Substring [%d %d] is not a "
"palindrome\n",
L, R);
}
else
printf("The Substring [%d %d] is not a "
"palindrome\n",
L, R);
}
return;
}
// A Dynamic Programming Based Approach to compute the
// powers of 101
void computePowers(unsigned long long int power[], int n)
{
// 101^0 = 1
power[0] = 1;
for (int i = 1; i <= n; i++)
power[i] = (power[i - 1] % MOD * p % MOD) % MOD;
return;
}
/* Driver program to test above function */
int main()
{
string str = "abaaabaaaba";
int n = str.length();
// A Table to store the powers of 101
unsigned long long int power[n + 1];
computePowers(power, n);
// Arrays to hold prefix and suffix hash values
unsigned long long int prefix[n + 1], suffix[n + 1];
// Compute Prefix Hash and Suffix Hash Arrays
computePrefixHash(str, n, prefix, power);
computeSuffixHash(str, n, suffix, power);
Query q[] = { { 0, 10 }, { 5, 8 }, { 2, 5 }, { 5, 9 } };
int m = sizeof(q) / sizeof(q[0]);
queryResults(str, q, m, n, prefix, suffix, power);
return (0);
}
Java
/* A Java program to answer queries to check whether
the substrings are palindrome or not efficiently */
public class GFG {
static int p = 101;
static int MOD = 1000000007;
// Structure to represent a query. A query consists
// of (L, R) and we have to answer whether the substring
// from index-L to R is a palindrome or not
static class Query {
int L, R;
public Query(int L, int R)
{
this.L = L;
this.R = R;
}
};
// A function to check if a string str is palindrome
// in the ranfe L to R
static boolean isPalindrome(String str, int L, int R)
{
// Keep comparing characters while they are same
while (R > L) {
if (str.charAt(L++) != str.charAt(R--)) {
return (false);
}
}
return (true);
}
// A Function to find pow (base, exponent) % MOD
// in log (exponent) time
static int modPow(int base, int exponent)
{
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return base;
}
int temp = modPow(base, exponent / 2);
if (exponent % 2 == 0) {
return (temp % MOD * temp % MOD) % MOD;
}
else {
return (((temp % MOD * temp % MOD) % MOD)
* base % MOD)
% MOD;
}
}
// A Function to calculate
// Modulo Multiplicative Inverse of 'n'
static int findMMI(int n)
{
return modPow(n, MOD - 2);
}
// A Function to calculate the prefix hash
static void computePrefixHash(String str, int n,
int prefix[], int power[])
{
prefix[0] = 0;
prefix[1] = str.charAt(0);
for (int i = 2; i <= n; i++) {
prefix[i] = (prefix[i - 1] % MOD
+ (str.charAt(i - 1) % MOD
* power[i - 1] % MOD)
% MOD)
% MOD;
}
return;
}
// A Function to calculate the suffix hash
// Suffix hash is nothing but the prefix hash of
// the reversed string
static void computeSuffixHash(String str, int n,
int suffix[], int power[])
{
suffix[0] = 0;
suffix[1] = str.charAt(n - 1);
for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++) {
suffix[j] = (suffix[j - 1] % MOD
+ (str.charAt(i) % MOD
* power[j - 1] % MOD)
% MOD)
% MOD;
}
return;
}
// A Function to answer the Queries
static void queryResults(
String str, Query q[], int m, int n,
int prefix[], int suffix[], int power[])
{
for (int i = 0; i <= m - 1; i++) {
int L = q[i].L;
int R = q[i].R;
// Hash Value of Substring [L, R]
long hash_LR
= ((prefix[R + 1] - prefix[L] + MOD) % MOD
* findMMI(power[L]) % MOD)
% MOD;
// Reverse Hash Value of Substring [L, R]
long reverse_hash_LR
= ((suffix[n - L] - suffix[n - R - 1] + MOD) % MOD
* findMMI(power[n - R - 1]) % MOD)
% MOD;
// If both are equal then the substring is a palindrome
if (hash_LR == reverse_hash_LR) {
if (isPalindrome(str, L, R) == true) {
System.out.printf("The Substring [%d %d] is a "
+ "palindrome\n",
L, R);
}
else {
System.out.printf("The Substring [%d %d] is not a "
+ "palindrome\n",
L, R);
}
}
else {
System.out.printf("The Substring [%d %d] is not a "
+ "palindrome\n",
L, R);
}
}
return;
}
// A Dynamic Programming Based Approach to compute the
// powers of 101
static void computePowers(int power[], int n)
{
// 101^0 = 1
power[0] = 1;
for (int i = 1; i <= n; i++) {
power[i] = (power[i - 1] % MOD * p % MOD) % MOD;
}
return;
}
/* Driver code */
public static void main(String[] args)
{
String str = "abaaabaaaba";
int n = str.length();
// A Table to store the powers of 101
int[] power = new int[n + 1];
computePowers(power, n);
// Arrays to hold prefix and suffix hash values
int[] prefix = new int[n + 1];
int[] suffix = new int[n + 1];
// Compute Prefix Hash and Suffix Hash Arrays
computePrefixHash(str, n, prefix, power);
computeSuffixHash(str, n, suffix, power);
Query q[] = { new Query(0, 10), new Query(5, 8),
new Query(2, 5), new Query(5, 9) };
int m = q.length;
queryResults(str, q, m, n, prefix, suffix, power);
}
}
// This code is contributed by Princi Singh
C#
/* A C# program to answer queries to check whether
the substrings are palindrome or not efficiently */
using System;
class GFG {
static int p = 101;
static int MOD = 1000000007;
// Structure to represent a query. A query consists
// of (L, R) and we have to answer whether the substring
// from index-L to R is a palindrome or not
public class Query {
public int L, R;
public Query(int L, int R)
{
this.L = L;
this.R = R;
}
};
// A function to check if a string str is palindrome
// in the ranfe L to R
static Boolean isPalindrome(String str, int L, int R)
{
// Keep comparing characters while they are same
while (R > L) {
if (str[L++] != str[R--]) {
return (false);
}
}
return (true);
}
// A Function to find pow (base, exponent) % MOD
// in log (exponent) time
static int modPow(int Base, int exponent)
{
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return Base;
}
int temp = modPow(Base, exponent / 2);
if (exponent % 2 == 0) {
return (temp % MOD * temp % MOD) % MOD;
}
else {
return (((temp % MOD * temp % MOD) % MOD) * Base % MOD) % MOD;
}
}
// A Function to calculate Modulo Multiplicative Inverse of 'n'
static int findMMI(int n)
{
return modPow(n, MOD - 2);
}
// A Function to calculate the prefix hash
static void computePrefixHash(String str, int n,
int[] prefix, int[] power)
{
prefix[0] = 0;
prefix[1] = str[0];
for (int i = 2; i <= n; i++) {
prefix[i] = (prefix[i - 1] % MOD
+ (str[i - 1] % MOD * power[i - 1] % MOD) % MOD)
% MOD;
}
return;
}
// A Function to calculate the suffix hash
// Suffix hash is nothing but the prefix hash of
// the reversed string
static void computeSuffixHash(String str, int n,
int[] suffix, int[] power)
{
suffix[0] = 0;
suffix[1] = str[n - 1];
for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++) {
suffix[j] = (suffix[j - 1] % MOD
+ (str[i] % MOD * power[j - 1] % MOD) % MOD)
% MOD;
}
return;
}
// A Function to answer the Queries
static void queryResults(String str, Query[] q, int m, int n,
int[] prefix, int[] suffix, int[] power)
{
for (int i = 0; i <= m - 1; i++) {
int L = q[i].L;
int R = q[i].R;
// Hash Value of Substring [L, R]
long hash_LR
= ((prefix[R + 1] - prefix[L] + MOD) % MOD
* findMMI(power[L]) % MOD)
% MOD;
// Reverse Hash Value of Substring [L, R]
long reverse_hash_LR
= ((suffix[n - L] - suffix[n - R - 1] + MOD) % MOD
* findMMI(power[n - R - 1]) % MOD)
% MOD;
// If both are equal then the substring is a palindrome
if (hash_LR == reverse_hash_LR) {
if (isPalindrome(str, L, R) == true) {
Console.Write("The Substring [{0} {1}] is a "
+ "palindrome\n",
L, R);
}
else {
Console.Write("The Substring [{0} {1}] is not a "
+ "palindrome\n",
L, R);
}
}
else {
Console.Write("The Substring [{0} {1}] is not a "
+ "palindrome\n",
L, R);
}
}
return;
}
// A Dynamic Programming Based Approach to compute the
// powers of 101
static void computePowers(int[] power, int n)
{
// 101^0 = 1
power[0] = 1;
for (int i = 1; i <= n; i++) {
power[i] = (power[i - 1] % MOD * p % MOD) % MOD;
}
return;
}
/* Driver code */
public static void Main(String[] args)
{
String str = "abaaabaaaba";
int n = str.Length;
// A Table to store the powers of 101
int[] power = new int[n + 1];
computePowers(power, n);
// Arrays to hold prefix and suffix hash values
int[] prefix = new int[n + 1];
int[] suffix = new int[n + 1];
// Compute Prefix Hash and Suffix Hash Arrays
computePrefixHash(str, n, prefix, power);
computeSuffixHash(str, n, suffix, power);
Query[] q = { new Query(0, 10), new Query(5, 8),
new Query(2, 5), new Query(5, 9) };
int m = q.Length;
queryResults(str, q, m, n, prefix, suffix, power);
}
}
// This code is contributed by Rajput-Ji
The Substring [0 10] is a palindrome The Substring [5 8] is not a palindrome The Substring [2 5] is not a palindrome The Substring [5 9] is a palindrome
Complejidad de tiempo: O(n*m) donde m es el número de consultas y n es la longitud de la string.
Espacio Auxiliar : O(n)
Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA