Algoritmo para encontrar palíndromos

Estoy publicar esto en nombre de un amigo ya que creo que esto es bastante interesante:

Tome la cadena "ABB". Al dejar fuera cualquier número de letras menor que la longitud de la cadena que termina con siete cuerdas.

ABB AB ab bb abb

De estos cuatro son palíndromos.

Del mismo modo para la cadena

"Hihellolookhavealookatthispalindromexxqwertyuiopasdfghjklzxcvbnmmnbvcxzlkjhgfdsapoiuytrewqxxsoundsfamiliardoesit"

(Una longitud de 112 cuerdas) 2 ^ 112 a 1 cadenas se pueden formar.

De estos cuántos son palíndromos?

A continuación se presenta su aplicación (en C + +, C también está bien sin embargo). Es bastante lento, con palabras muy largas, quiere saber cuál es el algoritmo más rápido posible para esto (y tengo curiosidad también: D).

 #include <iostream> #include <cstring> using namespace std; void find_palindrome(const char* str, const char* max, long& count) { for(const char* begin = str; begin < max; begin++) { count++; const char* end = strchr(begin + 1, *begin); while(end != NULL) { count++; find_palindrome(begin + 1, end, count); end = strchr(end + 1, *begin);}}} Int main (int argc, char * argv []) {const char * s = "hihellolookhavealookatthis" cuenta larga = 0; find_palindrome (s, strlen (s) + s, cuenta); cout <<contador << endl;} 

---

El usuario Autopulated respondió:

Hmm, creo que contaría así:

Cada personaje es un palíndromo por sí mismo (menos caracteres repetidos).
Cada par de la misma naturaleza.
Cada par de la misma naturaleza, con todos los palíndromos intercalado en el medio que se puede hacer de la cadena entre las repeticiones.
Aplicar de forma recursiva.

Que parece ser lo que estás haciendo, aunque no estoy seguro de que no duplicará la contabilización de los casos de borde con caracteres repetidos.

Así que, básicamente, no se me ocurre una mejor manera.

EDITADO:
Pensando un poco más, puede ser mejorado con almacenamiento en caché, porque a veces contar con los palíndromos en la misma sub-cadena de más de una vez. Por lo tanto, supongo que esto demuestra que definitivamente hay una mejor manera.

---

El usuario djna respondió:

¿Hay algún kilometraje en la toma de un recorrido inicial y la creación de un índice de todas las ocurrencias de cada personaje.

  h = { 0, 2, 27} i = { 1, 30 } etc. 

Ahora trabajo desde la izquierda, h, sólo palidromes posibles a los 3 y 17, se char [0 + 1] == char [3 -1], etc tiene un palíndromo. hace char [0 1] == char [27 -1] no, no un nuevo análisis de char [0] es necesario.

Pasar a char [1], sólo es necesario ejemplo char [30 -1] y hacia el interior.

A continuación, puede conseguir probablemente inteligente, cuando se ha identificado un palíndromo que va desde la posición x->, todos los subconjuntos internos se conocen palíndromos, por lo que hemos lidiado con algunos elementos, puede eliminar los casos de examen posterior.

---

El usuario RALU respondió:

No estoy seguro pero es posible que trate de Fourier ápice. Este problema me remined en esto: http://stackoverflow.com/questions/1560523/onlogn-algorithm-find-three-evenly-spaced-ones-within-binary-string

Sólo mi 2cents

---

El usuariocom/users/189205 'interjay> respondió:

En primer lugar, la solución de su amigo parece haber un error ya que strchr puede buscar últimos max . Incluso si usted solucionar este problema, la solución es exponencial en el tiempo.

Para una solución más rápida, puede utilizar la programación dinámica para resolver esta en O (n ^ 3) tiempo. Esto requiere O (n ^ 2) de memoria adicional. Tenga en cuenta que para las cadenas largas, incluso enteros de 64 bits que he utilizado aquí no será suficiente para mantener la solución.

 #define MAX_SIZE 1000 long long numFound[MAX_SIZE][MAX_SIZE]; //intermediate results, indexed by [startPosition][endPosition] long long countPalindromes(const char *str) { int len = strlen(str); for (int startPos=0; startPos<=len; startPos++) for (int endPos=0; endPos<=len; endPos++) numFound[startPos][endPos] = 0; for (int spanSize=1; spanSize<=len; spanSize++) { for (int startPos=0; startPos<=len-spanSize; startPos++) { int endPos = startPos + spanSize; long long count = numFound[startPos+1][endPos]; //if str[startPos] is not in the palindrome, this will be the count char ch = str[startPos];/ / Si la cadena [poslnicio] está en el palíndromo, elegir un personaje de contrapartida para el final palíndromo para (searchPos int = poslnicio; searchPos endPos <; searchPos + +) {if ([searchPos] str == ch) cuenta + = 1 + numFound [poslnicio 1] [searchPos];} numFound [poslnicio] [endPos] count =;}} return numFound [0] [len];} 

Explicación:

La matriz numFound[startPos][endPos] llevará a cabo el número de palíndromos que figuran en la subcadena con poslnicio índices endPos.

Repasamos todos los pares de índices (poslnicio, endPos), a partir de poca capacidad de movimiento y de los más largos. Para cada par, hay dos opciones:

1. El carácter en str[startPos] no está en el palíndromo. En ese caso, hay numFound[startPos+1][endPos] palíndromos posible - un número que hemos calculado ya.

2. carácter a la str[startPos] está en el palíndromo (en sus comienzos). Nos escanear a través de la cadena para encontrar un personaje que empareja para poner al final del palíndromo. Para cada personaje tal, se utiliza la calculada de los resultados ya en numFoundpara ver el número de posibilidades para el palíndromo interior.

EDITADO:

• Aclaración: cuando digo "el número de palíndromos contenidos en una cadena", esto incluye subcadenas no contiguos. Por ejemplo, el palíndromo "aba" figura en el "ABCA".

• Es posible reducir el uso de memoria a O (n), tomando ventaja del hecho de que el cálculo de numFound[startPos][x] sólo requiere el conocimiento de numFound[startPos+1][y] para todo y. No voy a hacer esto aquí, ya que complica el código un poco.

• Pregenerating listas de índices que contiene cada letra puede hacer que el lazo interno más rápido, pero aún así será O (n ^ 3) en general.

---

El usuario trinithis respondió:

Mi solución con O(n) la memoria y la O(n^2) el tiempo, donde n es la longitud de la cadena:

palindrome.c:

 #include <stdio.h> #include <string.h> typedef unsigned long long ull;countPalindromesHelper ull (const char * str, len const size_t, size_t const comienzo, final size_t constante, el recuento de ull const) {if (inicio <= 0 | | Final> = len) {return cuenta;} pred = const char str [comenzar - 1]; succ const char = str] final [if (pred succ ==) {newCount ull const = cuenta == 0? 1: * cuenta 2; countPalindromesHelper retorno (str, len, comenzará - 1, final + 1, newCount);} return cuenta;} countPalindromes ull (const char * str) {cuenta ull = 0; size_t len ​​= strlen (str) ; size_t i; for (i = 0; i <len; i + +) {cuenta + = countPalindromesHelper (str, len, i, i, 0); / / aun longitud palíndromos cuenta + = countPalindromesHelper (str, len, i , i + 1, 1); / / palíndromos de longitud impar} return cuenta;} int main (int argc, char * argv []) {if (argc <2) {return 0;} str const char * argv = [1 ]; ull count = countPalindromes (str); printf ("% llu \ n", cuenta); return 0;} 

---

Uso:

 $ gcc palindrome.c -o palindrome $ ./palindrome myteststring 

---

EDITADO:He leído mal el problema que la versión subcadena contiguos del problema. Ahora, dado que uno quiere encontrar el número capicúa para la versión no contiguos, tengo la firme sospecha de que uno sólo podría utilizar una ecuación matemática para resolver dado el número de caracteres distintos y sus recuentos de carácter social respectiva.

---

El usuario Bragboy respondió:

Aquí es un programa para encontrar todos los palíndromos posible en una cadena escrita en Java y C + +.

---

Este texto ha sido obtenida de esta fuente original en Stackoverflow.com

---

---