See discussions, stats, and author profiles for this publication at: [Link]

net/publication/331288034

Aplicaciones de Hash en String para la Programación Competitiva

Article · January 2019

CITATIONS READS
0 903

1 author:

Iván Galbán
University of Havana
3 PUBLICATIONS 0 CITATIONS

SEE PROFILE

All content following this page was uploaded by Iván Galbán on 24 April 2020.

The user has requested enhancement of the downloaded file.

Aplicaciones de Hash en String para la Programación Competitiva
Iván Galbán Smith
Facultad de Matemática y Computación, Universidad de La Habana
Cuba (email: [Link]@[Link])

Resumen
Este artı́culo contiene una implementación de una función hash en strings, donde se explican algunas
de sus aplicaciones y técnicas utilizadas en las competencias de programación ACM-ICPC. Brinda un
conjunto de funcionalidades y le da a los competidores otra forma de atacar los problemas a los que se
enfrentan con una solución en ocasiones fácil de implementar, donde tal vez la solución oficial puede ser
muy compleja y demorarı́a mucho tiempo idearla. Se presentan un conjunto de problemas tomados de
concursos anteriores, todos muy útiles ya que sus soluciones se enriquecen mutuamente.

1. Introducción
Muchas aplicaciones requieren un conjunto dinámico que da soporte solo a las operaciones de diccio-
narios INSERT, SEARCH y DELETE. Por ejemplo, un compilador para un lenguaje de computadoras
mantiene una tabla de sı́mbolos, en la cual los elementos llaves son arbitrarias cadenas de caracteres
que corresponden a identificadores del lenguaje. Una Hash Table es una efectiva implementación de dic-
cionarios. A pesar de que realizar una operación de búsqueda en una hash table puede demorar tanto
como buscar un elemento en una Linked List(θ(n) para el caso peor), en la práctica, las operaciones
de hash se ejecutan extremadamente bien (bajo la razonable suposición que el tiempo esperado para la
búsqueda en una hash table es O(1)). Una hash table es una generalización de la más simple noción de
un array ordinario. Direccionando directamente en un array ordinario hacemos uso de nuestra habilidad
de examinar una posición de un array en O(1) [1]. Las funciones de Hash constituyen hoy en dı́a de
gran importancia para la computación, desde una forma de implementar estructuras de datos para mini-
mizar complejidad temporal en sus operaciones, hasta su uso en seguridad, para encriptar información,
claves, etc. Numerosos libros como el Introduction To Algorithms[1] (pág 221) y The Art of Computer
Programming[2] (pág 506), por solo mencionar algunos de los más populares, le dedican capı́tulos enteros
para su explicación, buenas implementaciones y análisis de problemas a los que nos estamos arriesgando
con su uso, aunque existen métodos y modelos para minimizar estos problemas.

Este artı́culo se limita solo a mostrar una función de hash donde su dominio son cadenas de caracteres,
fácil de implementar, brindando numerosas funcionalidades y comodidades para resolver problemas de
programación competitiva, donde la solución de los problemas pueden ser a veces un poco complicada
de generar, y con este enfoque tal vez sea mucho más fácil desarrollar una solución que cumpla con las
restricciones del problema para ser aceptado.

2. String Hashing
Definición 2.1. Sea hash : A → N , una función de Hash donde el conjunto A contiene string y N es
un conjunto finito de números naturales, tal que hash(x) = y, donde x ∈ A y y ∈ N .
Definición 2.2. Sea S = s1 s2 s3 , . . . , sn una cadena de caracteres tal que S ∈ A y si representa el
i-ésimo caracter.
Definición 2.3. Una función de Hash, tiene colisiones si exite x ∈ A y y ∈ A, con x 6= y tal que
hash(x) = hash(y).
Primero veamos algunos de los aspectos a tener en cuenta para una función de hash.
1. Una función de Hash debe ser rápido de computar.

1
 2. Una función de Hash también debe distribuir las llaves tan uniformemente como sea posible en la
tabla de hash y evitar colisiones tanto como sea posible.
3. Una función de Hash debe ser consistente con la misma función.
a) Si dos llaves son iguales, la función de Hash debe mapearlas en la misma localización de la
tabla.
b) De lo contrario, las operaciones fundamentales de la tabla de Hash no funcionarán correcta-
mente.
Entonces, básicamente para un string S = s0 s1 s2 , . . . , sn−1 , nosotros queremos asignarle una único
número que puede ser calculado de la información almacenada en S.
Una función de Hash definida para S podrı́a ser la suma de sus caracteres. O sea
n−1
X
hash(S) = s0 + s1 + · · · + sn−1 = si
i=0

pero esto traerı́a como consecuencia la presencia de muchas colisiones, ya que todos los anagramas
de S tendrı́an la misma imagen en la función de Hash.
Por ejemplo, sea S = "Arlette" y S R = "ettelrA", es fácil evaluar y ver que hash(S) = hash(S R ) =
721.

Una función de Hash utilizada mucho en los concursos de programación ACM-ICPC, es:
n−1
X
hash(S) = ( si ∗ pi ) %M OD
i=0

Intuitivamente podemos ver que esta función de Hash es bastante buena ya que depende de la longitud
de la cadena y de las posiciones de los caracteres en la cadena. Note que calcular el hash de una cadena
con esta función es lo mismo que evaluar un polinomio por lo que la complejidad temporal es O(n).
Inteligentes selecciones de p y M OD ayuda a evitar colisiones. Trataremos de usar p y M OD como
primos, donde p tiene que ser mayor que el número de distintos elementos de nuestro alfabeto.
Veamos una implementación en C#.
s t a t i c long hash ( s t r i n g s , long x = 1 2 2 3 , long MOD = 1 0 0 0 0 0 0 0 0 9 )
{
long [ ] h = new long [ s . Length ] ;
long [ ] pow = new long [ s . Length ] ;
pow [ 0 ] = 1 ; h [ 0 ] = s [ 0 ] ;
f o r ( i n t i = 1 ; i < s . Length ; ++i )
{
pow [ i ] = ( pow [ i − 1 ] ∗ x ) %MOD;
h [ i ] = ( h [ i − 1 ] + s [ i ] ∗ pow [ i ] ) %MOD;
}
return h [ s . Length − 1 ] ;
}
Otro buen método es almacenar los hash en pares, donde cada uno corresponde a evaluar la función
de hash utilizando los primos M OD1 y M OD2 respectivamente, cuyo resultado seguramente hará más
peque***o el número de colisiones.

2
3. Problemas
3.1. Palindrome Substring
You have a string S of length N . You are given Q queries of form Li , Lj (i <= j). For each query,
print "YES", if substring denoted by SLi , SLi +1 , . . . , SRi is a palindrome. Both N, Q ≤ 105 .

3.1.1. Solución
Obviamente en este problema se necesita una solución mejor que usar fuerza bruta que es O(QN ).
Podemos calcular el hash de cualquier subcadena en O(1) realizando un preprocesamiento en O(N ).
Supongamos que deseamos calcular el hash(S[L, R]).
Definición 3.1. Sea F (R) = hash(S[0, R]) = ( R i
P
i=0 Si ∗ p ) %M OD
PR
Note que a que F (R) − F (L − 1) = ( i=L Si ∗ pi ) %M OD = hash(S[L, R]) ∗ pL .

Note que para determinar el hash(S[L, R]) necesitamos calcular inverso modular, de ahı́ la importan-
cia de que M OD sea un número primo.

Para responder las preguntas eficientemente, realizamos un preprocesamiento de prefijos y sufijos de

hash. Tal que pre[i] = hash(S[0, i]) y suf [i] = hash(S[i, 0]).

Sea h1 = (pre[r] − pre[l − 1] + M OD) %M OD = hash(S[L, R]) ∗ pL .

Sea h2 = (bh[l] − bh[r + 1] + M OD) %M OD = hash(S[R, L]) ∗ pn−r+1 .
Para saber si el subcadena S[L, R] es palı́ndroma solo necesitamos verificar si hash(S[L, R]) =
hash(S[R, L]). Como solo necesitamos conocer si ambos hash son iguales y no ası́ sus valores, no es
necesario el uso del inverso modular ya que en vez de dividir h1 entre pL y h2 entre pn−r+1 , podemos
solo comparar h1 ∗ pn−r+1 con h2 ∗ pL .
Existen numerosas formas de implementar este problema, a continuación se presenta una de ellas que
realiza un preprocesamiento O(N ) y responde Q preguntas en O(Q).

3.1.2. Implementación
C#: [Link]
[Link]

3
3.2. PLD - Palindromes
Tomado de: [Link]
A palindrome is a word, phrase, number or other sequence of units that has the property of reading
the same in either direction, e.g. "racecar", "solos".

Task
You are given a number k (2 ≤ k ≤ 30000) and a non-empty string S whose length does not exceed
30000 lowercase letters. We say two palindromes are different when they start from different positions.
How many different palindromes of the length k does S contains?

Input
The first line contains k. The second line contains S. k does not exceed the length of S.

Output
The first and only line should consist of a single number - the number of palindromes found.

Input Output
5 2
ababab

3.2.1. Solución
Como ya hemos visto la solución fuerza bruta no es muy buena para este tipo de problemas. Se
pudiera realizar una solución utilizando el algoritmo Manacher, pero su implementación lleva un poco
más de práctica por parte del programador y a veces complicada para algunos.
Utilizando lo aprendido en los problemas anteriores, podemos realizar una especie de fuerza bruta, uti-
lizando de soporte las funciones del problema anterior, tales como compute hash, substring palindrome
y prime power. Usando hash, con solo estas funciones podemos determinar como se explicó anteriormen-
te si una subcadena es palı́ndroma en O(1). Por lo que podemos iterar por todos las posibles subcadenas
en O(N ), llegando a la conclusión que la idea de solución propuesta es O(N ).

3.2.2. Implementación
C#: [Link]
cs

4
3.3. Longest Palindrome Substring
You have a string S of length N , you must to find the length of the longest palindrome substring of S.

Input:
Lı́nea 1: A string s (|s| ≤ 105 ).

Output:
The answers.

Sample Input Sample Output

siampabbay 4

3.3.1. Solución
La resolución de este problema es straightforward en O(n) utilizando el algoritmo Manacher, pero
este no es dominado por muchı́simos programadores, ya que su entendimiento pudiera ser complejo para
algunos que no dominan la Programación Dinámica.

La solución que se explica a continuación es otro de los provechos que podemos obtener dominando
y conociendo algunos trucos sobre hash en string. Utilizaremos funciones ya explicadas e implementadas
en problemas vistos anteriormente.

Anteriormente en el problema PLD - Palindromes (3.2) vimos como encontrar la cantidad de sub-
cadenas palı́ndromas de longitud k en O(n), por lo que una primera idea de solución serı́a iterar por cada
una de las posibles longitudes de las subcadenas de s, y quedarnos con la mayor longitud de subcadena
palı́ndroma. Esta idea es O(n2 ), por lo que no es muy buena.

Teorema 3.2. Si una cadena tiene una subcadena palı́ndroma de longitud k, con k > 1 entonces también
tiene una subcadena palı́ndroma de longitud k − 2, otra de longitud k − 4, k − 6, . . . .

Demostración. Inducción en k.
k=2
Consideremos por definición que una cadena de longitud 0 es palı́ndroma. Luego si s una cadena
cualquiera tiene una subcadena palı́ndroma de longitud 2, entonces por definición tiene una subcadena
palı́ndroma de longitud 0.

k=3
Sea s una cadena cualquiera y t = abc una subcadena de s que es un palı́ndromo de longitud 3 de s.
Es fácil ver que cualquier caracter perteneciente a s es palı́ndromo de longitud 1. Por lo que se cumple
que en s hay al menos una subcadena de longitud |t| − 2 = 1.

Hipótesis.
Supongamos que para toda cadena que tiene una subcadena palı́ndroma de longitud k se cumple que
también tiene subcadenas palı́ndromas de longitud k − 2, k − 4, . . . .

k ⇒k+2
Sea s una cadena cualquiera y sea t una subcadena de s que es un palı́ndromo de longitud k + 2.
Sea t = t1 t2 . . . tk+2 , entoces por definición de palı́ndromo se cumple que:
t1 = tk+2 , t2 = tk+1 . . .
O sea ti = tk+2−i+1 .
Luego sea p = t2 . . . tk+1 , se cumple que p es palı́ndromo y es subcadena de t por lo que también lo
es de s.
Como p es una subcadena de él mismo y es palı́ndromo y |p| = k, entonces p cumple Hipótesis de
Inducción y contiene subcadenas palı́ndromas de longitud k − 4, k − 6, . . . que también son subcadenas
palı́ndromas de t y por transitividad lo son de s.

5
 Aprovechando el Teorema 3.2, vemos que no es necesario iterar por todas las posibles subcadenas,
es posible realizar dos búsquedas binaria en la longitud de las subcadenas palı́ndromas, una para las
subcadenas de tamaño par y la otra para las de tamaño impar y luego proceder a determinar en O(n)
si existe alguna subcadena palı́ndroma con esa longitud en la cadena original. Realmente no es necesario
implementar dos búsquedas binarias, con solo una basta, indicándole por parámetro la paridad de la
longitud de las subcadenas que estamos buscando.

3.3.2. Implementación
C#: [Link]
palindrome_substring.cs

3.3.3. Complejidad
No es muy difı́cil ver que la complejidad de nuestro algoritmo viene dado por la busqueda binaria y
la complejidad de la función que en ella se evalúa.
Podemos ver que la complejidad es:
n
T (n) = T ( ) + O(n)
2
Resolviendo la recurrencia el algoritmo propuesto es O(n log n).

6
3.4. Bipalı́ndromo
Tomado de: [Link]
Dada un cadena de caracteres S (1 ≤ |S| ≤ 1000000) se desea saber cuántas particiones existen de S
en otras dos cadenas (contando la cadena vacı́a), tal que ambas sean palı́ndromos.

Entrada
Lı́nea 1: En la primera lı́nea estará la cadena de caracteres S.

Salida
Lı́nea 1: En la primera lı́nea deberá estar un único entero N que representa la cantidad veces que se
puede particionar la cadena S en dos palı́ndromos.

Ejemplo de entrada Ejemplo de salida

ababab 3

Hints
Las biparticiones de la cadena "ababab" son:
{"", "ababab"} la 1era cadena no es palı́ndromo
{"a", "babab"} ambas son palı́ndromo
{"ab", "abab"} ninguna cadena es palı́ndromo
{"aba", "bab"} ambas son palı́ndromo
{"abab", "ab"} ninguna cadena es palı́ndromo
{"ababa", "b"} ambas son palı́ndromo
{"ababab", ""} la 2da cadena no es palı́ndromo

3.4.1. Solución por Algoritmo KMP

A continuación veremos como resolver este problema como String Matching, donde la idea de solu-
ción es más compleja que la propuesta utilizando Hash, se basa en usar el algoritmo de Programación
Dinámica Knuth-Morris-Pratt (KMP) [3].
Definición 3.3. Sea S = XY una cadena cualquiera y X, Y biparticiones cualesquiera de S(recuerde
que en este problema tanto X como Y pueden ser la cadena vacı́a).
Definición 3.4. Se define a S R como el reverso de la cadena S y a SS como la concatenación de la
cadena S con ella misma.
Definición 3.5. Sea match(t, p) una función que devuelve verdadero si la cadena p es una subcadena
de la cadena t.
Teorema 3.6. match(XY XY, S R ) ≡ X y Y son ambas palı́ndromas.

Demostración. match(XY XY, S R ) ⇒ X y Y

Sin pérdida de generalidad supongamos que las particiones elegidas de X y Y son aquellas que hacen
Y X = SR.
Como S R = Y R X R , tenemos que Y X = Y R X R .
Sabemos que |Y | = Y R y |X| = X R .
∴ X = X R y Y = Y R.
⇒ X y Y son ambas palı́ndromas.

X y Y son ambas palı́ndromas ⇒ match(XY XY, S R )

Por Hipótesis tenemos que X = X R y Y = Y R .
Luego Y R X R = S R = Y X
⇒ match(XY XY, S R ) es verdadera

7
3.4.2. Solución por Hash
Este problema puede ser resuelto de la misma forma en que hemos resuelto los dos anteriores. Podemos
ir simulando las particiones con un puntero que se desplaza por la posición donde se divide el string y
llamar a la función substring palindrome exactamente de la misma forma en que lo hicimos anteriormente.
Logrando obtener una complejidad temporal O(N ). Sin más veamos como quedarı́a la implementación
de esta idea.

3.4.3. Implementación
C#: [Link]
cs

8
3.5. String Matching
Dado un texto T y un patrón P , se desea conocer la cantidad de veces que aparece el patrón P en el
texto T .

Entrada
Linea 1: El texto T , con |T | ≤ 105 .
Linea 2: El texto P , con |P | ≤ T .

Salida
Una única lı́nea que contiene un solo entero representando la cantidad de ocurrencias de P en T .

Ejemplo de Entrada Ejemplo de Salida

abasielmatiabat dlea baaba. 3
aba

3.5.1. Solución
Este es el clásico problema de string matching, que puede ser resuelto con fuerza bruta en O(mn),
donde |T | = n y |P | = m. Una buena solución en cuanto a complejidad temporal se puede hacer usando
el algoritmo KMP [3] en O(m + n), pero este puede ser complejo para algunos programadores. Por lo que
a continuación explicaremos como resolver este problema usando hash que es muy parecida al algoritmo
de Fuerza Bruta.

Para determinar la ocurrencia de un patrón P en un texto T , podemos seguir la misma idea del
algoritmo de Fuerza Bruta para determinar por cada subcadena de longitud m en T y comprobar en
O(1) si esta subcadena es igual a P . Recordemos que para conocer si una cadena s1 es igual a otra s2 ,
podemos verificar que hash(s1 ) = hash(s2 ). No olvidar que como estamos trabajando con hash, podrı́an
existir colisiones y nuestro algoritmo no funcionar correctamente, por lo que esta idea no es 100 % segura,
ası́ como el uso de ningún algoritmo probabilı́stico, lo único que podemos hacer como programador es
disminuir las probabilidades de fallar, y en el caso particular de este problema disminuir las probabilidades
de colisón. Para esto ya vimos en la sección 2 algunas estrategias.
Veamos un pseudocódigo para entender lo previamente explicado.
input T
input P
let match = 0
for i in [0..|T|-|P|]
if get_substring_hash(T, i, i+|P|-1) == get_hash(P)
match++
print match

9
3.5.2. Implementación
C#: [Link]
[Link]

3.5.3. Complejidad
Al principio se construye en O(n) el array de prefijos de hash de T , y además se calcula el hash de P
en O(m). Luego por cada subcadena de longitud m en T que son exactamente n − m + 1, se determina
su hash en O(1) y se compara con el de P en O(1) ya que ya lo habı́amos calculado anteriormente. Por
lo tanto nuestro algoritmo tiene una complejidad O(m + n), pero como m ≤ n ⇒ O(m + n) = O(n),
quedando ası́ la complejidad de la solución.

10
3.6. C. Watto and Mechanism
Tomado de: [Link]
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output
Watto, the owner of a spare parts store, has recently got an order for the mechanism that can
process strings in a certain way. Initially the memory of the mechanism is filled with n strings. Then
the mechanism should be able to process queries of the following type: "Given string s, determine if the
memory of the mechanism contains string t that consists of the same number of characters as s and
differs from s in exactly one position".
Watto has already compiled the mechanism, all that’s left is to write a program for it and check it
on the data consisting of n initial lines and m queries. He decided to entrust this job to you.

Input
The first line contains two non-negative numbers n and m (0 ≤ n ≤ 3 ∗ 105 , 0 ≤≤ 3 ∗ 105 ) - the
number of the initial strings and the number of queries, respectively.
Next follow n non-empty strings that are uploaded to the memory of the mechanism.

Next follow m non-empty strings that are the queries to the mechanism.

The total length of lines in the input doesn’t exceed 6∗105 . Each line consists only of letters ’a’, ’b’, ’c’.

Output
For each query print on a single line "YES" (without the quotes), if the memory of the mechanism
contains the required string, otherwise print "NO" (without the quotes).

Input Output
23 YES
aaaaa NO
acacaca NO
aabaa
ccacacc
caaac

3.6.1. Solución
La idea a seguir en este problema es ir insertando en un array los hash asociados a cada uno de los
n string que la estructura debe almacenar.
Una vez guardado todos esos valores procedemos a ordenar el array, con el objetivo de que si se
desea conocer si un determinado string fue almacenado en la estructura, solo es necesario buscar su hash
utilizando búsqueda binaria.
En este problema se desea conocer para cada pregunta si la cadena dada existe en dicha estructura
con solo uno de sus caracteres cambiado.
Para esto, sea s una cadena de entrada para una pregunta.
Se desea conocer si cambiando un caracter de s por otro diferente, la cadena resultante pertenece a
nuestra estructura.
Como la forma que tenemos de saber si una cadena pertenece a nuestra estructura es buscar su hash
en nuestro array en O(log n), entonces la idea serı́a recalcular en O(1) el hash de s resultante de cambiar
una posición cualquiera por otro caracter. Como es necesario comprobar para la cadena s, cambiar a lo
sumo todas las posiciones yP por cada una de ellas todos los posibles
P caracteres, entonces cada pregunta
puede ser respondida en O(| | |s| log n) = O(|s| log n), donde | | = 3 es la cardinalidad del alfabeto, por
lo que responder todas las preguntas tendrı́a una complejidad O(S log n), donde S = |s1 |+|s2 |+· · ·+|sm |
y |si | es la longitud de la cadena de entrada en la pregunta i-ésima.
∴ La complejidad de esta solución es O(L log n), donde L es la longitud de todas las cadenas.

11
3.6.2. Implementación en C#
Nota: En esta implementación se ha utilizado la estructura SortedSet<T> brindada en el lengueje
C# que permite insertar llaves y preguntar si contiene una llave dada en O(log N ), donde N es la canti-
dad de elemento insertados en el SortedSet. La idea no difiere a la explicada con un array y la búsqueda
binaria, ambas son en esencia lo mismo, una se utilizó para una mejor explicación hacia el lector, y la
otra es mejor para un concursante que está compitiendo bajo un tiempo.

C#: [Link]

3.6.3. Implementación en C++

C++: [Link]
cpp

12
3.7. 1286 - Palindrome Concatenation
Tomado de: [Link]
Description
Palindrome is considered to strings that are read the same way in any direction (left-right or right-
left). You must determine when a given chain can be expressed as the concatenation of palindromes
strings of even length.

Input specification
The first line contains a T , the number of test cases. We continue to T lines, each with the chain for
that test case. The string length is less than 106 .

Output specification
The output consists of T lines, one for each test case. Should be printed on each line Y ES if the
string can be expressed as strings palindromes and N O otherwise.

Sample input Sample output

4 NO
madam NO
aA YES
aabb NO
AA

3.7.1. Solución
En este problema se propone una solución Greedy que se apoya en los conocimientos aprendidos sobre
hash utilizando algunas de sus aplicaciones como determinar si una subcadena es palı́ndroma en O(1),
realizando un precómputo en O(n) (ver problema Palindrome Substring (3.1)).

Observación 3.7. Toda cadena palı́ndroma de longitud par tiene dos caracteres iguales como centro.
Definición 3.8. Sea s una cadena de caracteres cualquiera, un intervalo [l, r] se le llama palı́ndromo si
y solo si la subcadena s[l . . . r] es palı́ndroma.
La idea de nuestro algoritmo es ir llevando un puntero de donde debe ser el comienzo del intervalo
palı́ndromo de longitud par a determinar en ese momento. Note que al principio el puntero está inicializado
a 0.
Supongamos que ya hemos encontrado i − 1 intervalos palı́ndromos de longitud impar.
Sean [l1 , r1 ], [l2 , r2 ], . . . , [li−1 , ri−1 ], dichos intervalos. Veamos que nuestro puntero ptr = ri−1 + 1.
Por lo que el comienzo del nuevo intervalo a determinar será ptr.
Procedemos por cada idx ∈ (ptr, |s|), si se cumple que s[idx] = s[idx − 1], entonces idx y idx − 1, son
candidatos a medio para un subintervalo palı́ndromo de longitud par. Una vez fijado los caracteres del
medio y la posición del comienzo del intervalo (ptr), es fácil encontrar el simétrico de ptr sobre los medios
idx y idx − 1, llamémosle ptr0 . Ahora podemos verificar en O(1) si el intervalo [ptr, ptr0 ] es palı́ndromo.
En caso afirmativo, entonces se cumple que el intervalo [ptr, ptr0 ] será un intervalo de la solución por lo
que el nuevo intervalo a determinar comenzará en la pŕoxima posición donde terminá el anterior, o sea,
se procede a hacer ptr = ptr0 + 1. Este proceso se repite hasta que se llegue al final de la cadena.
A continuación se encuentra una solución en C# del problema, y luego una demostración de su
correctitud.

3.7.2. Implementación
C#: [Link]

3.7.3. Demostración
Aunque en el problema solo hay que determinar si una cadena dada es la concatenación de palı́ndro-
mos de longitud par, con solo una pequeña modificación a nuestro algoritmo se puede devolver también

13
una posible secuencia de intervalos correspondientes a dichos palı́ndromos. La demostración del algorit-
mo se realiza suponiendo que hay que devolver una de las distintas secuencias, lo cual demostrará su
correctitud al devolver Y ES si encuentra alguna secuencia y N O en caso contrario.

Sea X =< x1 , x2 , . . . , xn > la solución del algoritmo propuesto, que es Greedy.

Sea Y =< y1 , y2 , . . . , ym >, la solución óptima, se define como solución óptima aquella que minimiza
la cantidad de intervalos.
Por lo que se cumple que n ≥ m.

Si X = Y , ya está demostrado.
6 Y , notar que nunca sucederán los siguientes casos.
Si X =
1. n 6= 0 ∧ m = 0.
Esto es una contradicción ya que la solución greedy devolvió una secuencia válida de intervalos
que representan inicio y fin de la subcadenas asociadas que tienen longitud par y son palı́ndromas
pertenecientes a una partición de la cadena original.
n = 0 ∧ m 6= 0
Contradicción, ya que n ≥ m.
Luego, sea i la primera posición donde xi 6= yi .
Sean xi = [li , ri ] y yi = [li , ri0 ].

Observación 3.9. Necesariamente se cumple que ri0 > ri .

   
l +r 0
Demostración. Sean m = li +r
2
i
y m0 = i 2 i
Si ri0 < ri ⇒ [li , ri0 ] = xi ya que se cumplirı́a que s[m0 − 1] = s[m0 ] y m0 < m, por lo que el algoritmo
greedy al estar analizando la posición m0 hubiera encontrado que el intervalo [li , ri0 ] es palı́ndromo y lo
hubiese añadido a la solución.

∴ ri < ri0 ⇒ m < m0 .

Demostraremos que el intervalo [li , ri0 ] se puede dividir en otros tres intervalos palı́ndromos de longitud
par, donde el primer intervalo es exactamente igual a xi .
Como s[li . . . ri0 ] es palı́ndromom y sea li0 = ri0 − |xi | + 1 entonces se cumple que s[li . . . ri ] = s[li0 . . . ri0 ],
ya que s[li0 . . . ri0 ] es el intervalo simétrico a la derecha de los centros m y m0 del intervalo s[li , ri ]. De
donde s[li , ri ] es palı́ndromo ya que xi = [li , ri ] y s[li0 . . . ri0 ] también lo es ya que xi = [li0 . . . ri0 ].
Realizando un análisis similar al anterior, se obtiene que s[ri + 1 . . . m − 1] = s[m + 1 . . . li0 − 1], por
lo que s[ri + 1 . . . li0 − 1] es palı́ndromo.

∴ Los tres subintervalos palı́ndromos son:

[li . . . ri ], [ri + 1, li − 1], [li0 , ri0 ]

Luego la solución óptima se puede transformar en la solución greedy después de un número finito de
operaciones.
∴ Si para una cadena de entrada, la respuesta es YES, entonces la solución óptima encontró una
secuencia de intervalos que se pueden particionar llegando a obtener la solución greedy propuesta en
nuestro algoritmo, por lo que devolverá correctamente YES.
De lo contrario, si la respuesta correcta es NO, entonces nuestro algoritmo va tomando intervalos
contiguos palı́ndromos de longitud par, hasta que llegará un momento en el que no podrá encontrar
ninguno de estos intervalos, por lo que devolverá N O.

14
3.8. The Big Painting
Tomado de: [Link]
Description
Samuel W. E. R. Craft is an artist with a growing reputation. Unfortunately, the paintings he sells do
not provide him enough money for his daily expenses plus the new supplies he needs. He had a brilliant
idea yesterday when he ran out of blank canvas: ”Why don’t I create a gigantic new painting, made
of all the unsellable paintings I have, stitched together?”. After a full day of work, his masterpiece was
complete.
That’s when he received an unexpected phone call: a client saw a photograph of one of his paintings
and is willing to buy it now! He had forgotten to tell the art gallery to remove his old works from the
catalog! He would usually welcome a call like this, but how is he going to find his old work in the huge
figure in front of him?
Given a black-and-white representation of his original painting and a black-and-white representation
of his masterpiece, can you help S.W.E.R.C. identify in how many locations his painting might be?

Input specification
The first line consists of 4 space-separated integers: hp wp hm wm, the height and width of the painting
he needs to find, and the height and width of his masterpiece, respectively (1 ≤ hp ≤ hm ≤ 2, 000 and
1 ≤ wp ≤ wm ≤ 2, 000).
The next hp lines have wp lower-case characters representing his painting. After that, the next hm
lines have wm lower-case characters representing his masterpiece. Each character will be either ’x’ or ’o’.

Output specification
Output a single integer representing the number of possible locations where his painting might be,
on a line by itself.

Sample input Sample output

4 4 10 10 4
oxxo
xoox
xoox
oxxo
xxxxxxoxxo
oxxoooxoox
xooxxxxoox
xooxxxoxxo
oxxoxxxxxx
ooooxxxxxx
xxxoxxoxxo
oooxooxoox
oooxooxoox
xxxoxxoxxo

15
3.8.1. Solución
En este problema usaremos una idea parecida a la que hemos usado anteriormente en el problema
3.5, con la diferencia que el texto y el patrón son matrices, o sea, queremos hacer String Matching en
dos dimensiones. Es necesario también tener conocimientos sobre el trabajo con tablas acumulativas, ya
que la solución que se propone hace uso de una matriz de sumas acumuladas.

Definición 3.10. Sea la matriz del texto T , de nt y mt filas y columnas respectivamente. Sea P el
patrón a buscar en T , con np y mp filas y columnas respectivamente.
Definición 3.11. La función hash de una matriz de caracteres M , de n filas y m columnas respectiva-
mente es:
Xn X
m
hash(M ) = M [i][j] ∗ xi ∗ y j %M OD
i=1 j=1

, donde x, y son dos primos distintos, ambos mayores que la cardinalidad del alfabeto sobre el que está
definido M y M OD un número primo grande.
Se almacena en una matriz llamada ht, de tamaño igual a las dimensiones del texto el valor del hash
de las submatrices prefijos de T . Más formalmente:

ht[i][j] = hash(T [1..i][1..j])

Veamos como calcular la matriz ht[i][j], haciendo uso de la Programación Dinámica.

j
i−1 X j−1
i X j−1
i−1 X
X X X
ht[i][j] = T [i][j] ∗ xi ∗ y j + T [f ][c] ∗ xf ∗ y c + T [f ][c] ∗ xf ∗ y c − T [f ][c] ∗ xf ∗ y c
f =1 c=1 f =1 c=1 f =1 c=1
| {z } | {z } | {z }
ht[i−1][j] ht[i][j−1] ht[i−1][j−1]

⇒
ht[i][j] = T [i][j] ∗ xi ∗ y j + ht[i − 1][j] + ht[i][j − 1] − ht[i − 1][j − 1]
Por lo que se cumple que:

hash(T [i1 ..i2 ][j1 ..j2 ]) ∗ xi1 ∗ tj1 = ht[i2 ][j2 ] − ht[i2 − di ][j2 ] − ht[i2 ][j2 − dj] + ht[i2 − di ][j2 − dj ]

Siendo di = i2 − i1 + 1 y dj = j2 − j1 + 1.

Observación 3.12. En las fórmulas anteriores no se han incluido las operaciones de módulo necesarias,
para una mayor facilidad de visualización, buscando mejor entendimiento. Le dejamos al lector, a que
vea en la implementación como quedarı́a todo el resultado expresado módulo M OD.
De esta forma podemos conocer el hash de cualquier submatriz en O(1), por lo que por cada posición
de la matriz del texto T , verificamos en caso de existir si la submatriz de T con lı́mite inferior derecho
en la posición i, j y de tamaño np, mp, tal que su hash sea igual al del patrón a buscar.

Formalmente se desea ver si:

hash(T [i − n + 1..i][j − m + 1..j]) = hash(P )

16
3.8.2. Implementación
C++: [Link]
cpp
C#: [Link]

3.8.3. Complejidad
Sea n = nt, m = mt, n0 = np y m0 = mp.
Contruir la matriz ht es O(nm) y calcular el hash del patrón es O(n0 m0 ). Luego como se recorren
todas las posiciones del texto (hay nm posiciones) y en cada una se realiza O(1) de tiempo, entonces
nuestro algoritmo tiene una complejidad O(nm + n0 m0 + nm), como n0 ≤ m ∧ m0 ≤ m, la complejidad
temporal de la solución es O(nm).

17
 Referencias
[1] Tomás H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algo-
rithm, Second Edition, pp. 224-252, The MIT Press Cambridge, Massachusetts, McGraw-Hill Book
Company, (2001)
[2] Donald E. Knuth, The Art Of Computer Programming, Volumen 3, First Edition, pp. 506-549,
Addison-Wesley, (1973)
[3] Donald E. Knuth, James H. Morris, Vaughan R. Pratt, Fast Pattern Matching in Strings, Vol. 6,
No. 2, SIAM J. COMPUT. (1977)

18

View publication stats