Encontrar todos los palíndromos
por Rodrigo Burogs Dominguez
Un problema clásico de palíndromo es el de encontrar el numero de palíndromos distintos que hay en una cadena, la forma mas trivial para buscar todos estos palíndromos es buscar todas las posibilidades. Por ejemplo el algoritmo siguiente resuelve el problema:
1 long long countPalindromes( char *cad){
2 int cont = 0;
3 for( int izq = 0; izq < strlen( cad ) ; izq++)
4 for( int der = izq ; der < strlen( cad ) ; der++)
5 if( isPalindrome( cad, izq, der ) )
6 cont++;
7 return cont;
8 }
Este algoritmo valida todas las posibles posiciones para encontrar un palíndromo, que son las que determinan los punteros de estas posición izq y der, Como se puede apreciar la complejidad es de O(n^2 * complejidad _de( isPalindrome)).
Si el método de isPalindrome fuera el siguiente.
1 int isPalindrome( char *cad, int izq, int der){
2 if( izq >= der ) return 1;
3 return ( cad[izq] ¡= cad[ der ] ) ? 0 : isPalindrome( cad , izq + 1, der - 1));
4 }
Este método recorre linealmente la posición de izquierda a derecha, incrementando la posición izquierda y disminuir la posición derecha hasta que izquierda sea igual o mayor que derecha y por lo tanto el algoritmo de countPalindrome es de complejidad O(n^3), este es el primer acercamiento para resolver el problema de calcular todos los palíndromos, pero cuando el valor de n se incrementa el tiempo de ejecución se vuelve cada vez mas lento y para remediar eso necesitamos cambiar la forma de resolver el problema, esto lo podemos hacer utilizando programación dinámica (Véase el capitulo Programación Dinámica), modificamos este algoritmo de la siguiente manera:
1 int din[MAXLEN + 1][ MAXLEN + 1];
2 int isPalindrome( char *cad, int izq, int der){
3 if( izq >= der ) return 1;
4 if( din[izq][der] != -1) return din[izq][der];
5 din[izq][der] = 0;
6 if( cad[izq] == cad[der])
7 din[ izq ][der] = isPalindrome( cad , izq + 1, der - 1);
8 return din[izq][der];
9 }
Para que este algoritmo funcione la matriz din debe estar inicializada con -1, marcando esta posición como no visitada, al final esta función realizara (n^2) operaciones en todas las llamadas que se le haga, y la complejidad de countPalindrome ya no seria de O(n ^ 3) si no de O( n^2 + n^2).
Veamos la tabla siguiente para analizar el comportamiento de estos algoritmos:
Largo de la cadena | O(n^3) | O(n^2) |
100 | 1000000 | 10000 |
1000 | 1000000000 | 1000000 |
10000 | 1000000000000 | 100000000 |
Como puede uno observar en la tabla anterior el crecimiento es muy significativo en el primer algoritmo para un caso particular de 100 elementos tanto como el primero como el segundo pueden resolver el problema en menos de 1 segundo, para el segundo caso el primer algoritmo ya es muy lento y el segundo aun cumple con sacar la información en menos de 1 segundo. Pero para el tercer caso ambos algoritmos son muy lentos. Pero que podemos hacer con cadenas muy grandes de las cuales tenemos la misma interrogante, ¿encontrar todos los palíndromos? , existe un algoritmo que encuentra todos los palíndromos de una cadena dada en tiempo lineal y lo veremos a continuación.
Algoritmo de Manacher
El algoritmo de Manacher encuentra en tiempo lineal el número de palíndromo distintos que existen en una cadena, primero hay que definir algunas propiedades para poder pasar al algoritmo como tal.
Definamos Σ como un alfabeto finito. Un elemento Σ∗ es llamado una cadena. El largo de la cadena w se denota como |w|. Una cadena vacía ε es una cadena de largo 0, esto quiere decir que |ε|=0. Definamos Σ+ =Σ∗ − {ε} .
Una cadena w es llamada palíndromo si w = wR donde wR es la cadena invertida de w. Si |w| es par entonces w es llamado un palíndromo par, esto es, w = xxR para algún x ∈ Σ+. Pero si |w| es impar entonces es llamado un palíndromo impar, esto es, w = xaxR para algún x ∈ Σ∗ and a ∈ Σ. El radio de un palíndromo w es |w|.
Vamos a resolver primero los palíndromos impares, los centros de un palíndromo impar expresado como w = xaxR es a este centro tiene una longitud (|w | - 1)/2, el algoritmo va barriendo un arreglo de izquierda a derecha, supongamos que nosotros vamos recorriendo la cadena de la posición 0 a la posición |w| - 1, con la variable position, el proceso estaría calculando para cada position el largo del palíndromo y los extremos del palíndromo mas grande que se puede formar partiendo de la posición position como centro.
Posición izquierda: 0 Position: 1 Posición derecha: 2 |
W = | A | A | A | C | D | C | A | A |
Como se puede apreciar en el ejemplo anterior en la posición 1 se toma como centro, el lado izquierdo del palíndromo llega esta la posición 0 y el lado derecho hasta el 2. Este es el máximo palíndromo que se puede formar tomando como centro la posición 1, si nosotros tomáramos la posición 4 en donde se muestra una flecha roja, el lado izquierdo seria 1 y el lado derecho seria 7, este seria el máximo palíndromo que podemos formar cuyo centro esta en la posición 4.
Guardemos en un arreglo LP (largo del palíndromo) el largo del palíndromo cuyo centro este en la posición position (en el ejemplo LP[1] = 1, LP[4] = 3).
La base del algoritmo es apoyarse en el conocimiento que se tiene de los palíndromos anteriores, cuando nosotros nos encontramos en la posición position, las posiciones {1, 2, 3, ... position – 1} ya debieron ser calculadas, es por ello que sabemos cual es palíndromo que llega mas a la derecha de.
W | W[0] | ... | W[pi] | ... | W [pi+pd-position] | ... | W[mcenter] | ... | W[ position] | ... | W[pd] |
Veamos los casos, que pasa si nuestra posición position esta dentro de un palíndromo cuyo centro esta en mcenter , su lado izquierdo inicia en la posición izquierda (pi) y termina en la posición derecha (pd) se sabe que el largo LP[position] debería ser igual a lo largo de la posición contraria del palíndromo cuyo centro es mcenter, esto quiere decir que este elemento debe estar igual de lejos a pi que position de pd, entonces la nueva position debe estar a igual distancia que pd – position por tanto debe estar en pi +( pd – position) el elemento que buscamos, este elemento es el espejo de position , pero del lado contrario de mcenter.
LP[ position ] es igual a LP[ pi + ( pd - position]] siempre y cuando LP[pi - position] sea menor a pd - position , ¿por que menor? Si fuera mayor quiere decir que este palíndromo se extiende mas allá del palíndromo cuyo centro esta en mcenter donde suponemos que es simétrico a nuestra posición y por ello solo podemos estar seguros que nuestra posición tiene un palíndromo menor o igual a pd – position – 1, entonces hay que ver si del lado derecho sigue creciendo este palíndromo o no, esto lo podemos hacer recorriendo mas a la derecha y validando que siga siendo palíndromo que tendría centro en position.
Si es igual a (pd – position) entonces el palíndromo termina exactamente donde empieza el palíndromo cuyo centro es mcenter y del cual nos estamos basando para nuestra suposición, con esto sabemos que del lado izquierdo de mcenter no pudo crecer el palíndromo en la posición pi + pd – position pero como termina exactamente en los linderos de este palíndromo es posible que por el lado derecho pueda crecer aun mas.
Para el caso de que es menor no hay necesidad de ver si crece por que es simétrico el lado derecho del palíndromo con el lado izquierdo, por tanto no va a seguir creciendo mas que lo que ya ah crecido del lado izquierdo.
Con esta información podemos crear un algoritmo que corra en tiempo lineal veamos el algoritmo;
Declaramos las variables;
char W[MAXLEN + 1];
int LP[MAXLEN + 1];
int position, posizq, posder;
Leemos la cadena en W y proseguimos con el algoritmo
memset( LP, 0, sizeof( LP )); // inicializamos en 0 a LP
length = strlen( W );
pi = pd = -1;
for( position = 0 ; position < length ; position++){
currentLength = 0;
if( position <= pd )
currentLength = min( pd - position , LP[ pi + pd – position ]) + 1;
while( position – currentLength >= 0
&& position + currentLength < length
&& W[position - currentLength] == W[ position + currentLength])
currentLength++;
LP[ position ] = --currentLength;
if( position + currentLength > pd ){
pd = position + currentLength;
pi = position – currentLength;
}
}
Bueno ya resolvimos el problema para los palíndromos impares ahora vamos a resolverlo para los palíndromos pares, el proceso es el mismo solo cambian algunas cuantas restas mas. Aquí como tal no hay un centro entonces cuando hablamos del centro mcenter estamos hablando de la posición mcenter y mcenter – 1. Si suponemos esto el algoritmo quedaría asi:
Declaramos un nuevo arreglo LP2 (el largo del palíndromo par).
int LP2[MAXLEN + 1];
Después el algoritmo;
pi = pd = -1;
for (position = 0; position < length ; position++ ) {
currentLength = 0;
if( position <= pd){
currentLength=min( pd – position + 1,LP2[pi+pd–( position + 1) ])+1;
}
while( position – currentLength >= 0
&& position + currentLength – 1 < length
&& W[position - currentLength]== W[position + currentLength - 1])
currentLength++;
LP2[ position ] = --currentLength;
if (position + curreLength -1 > pd){
pi = position – currentLength;
pd = position + currentLenght - 1;
}
}
Con las dos partes del algoritmo ya tenemos todos los palíndromos que existen en una cadena W, en una manera mas simplificada en vez de tener una matriz de posición izquierdo y derecha, podemos almacenar la información en un solo vector ( en este caso dos) basándonos en el centro de los palíndromos.
Máximo palíndromo en una cadena
Como podemos encontrar el tamaño del máximo palíndromo que se encuentra en una cadena, como vimos en la sección pasada podemos buscar todas los palíndromos con una complejidad O( n^3) , O(n^2) o bien O( n ).
La forma más rápida en cuestión de codificar es la que se mostro con complejidad O(n ^2) pero si quiérenos la mejor eficacia lo único hay que hacer es codificar el algoritmo de Manacher y con los arreglo LP y LP2 realizar la siguiente operación:
lengthMaxPalindromo = 0;
for( x = 0; x < strlen(W); x++){
lengthMaxPalindromo = max( lengthMaxPalindromo , LP[x]* 2 + 1);
lengthMaxPalindromo = max( lengthMaxPalindromo , LP2[x]* 2 );
}
La solución se encuentra en lengthMaxPalindromo.
No hay comentarios:
Publicar un comentario