Antes que nada debemos leer una palabra y el tamaño deseado.
Luego, necesitamos encontrar el palíndromo más largo creado por los caracteres en esta palabra utilizada en orden.
Por ejemplo, para size = 7 y word = "abcababac" la respuesta es 7 ("abababa").
Postdata: el tamaño de la palabra es menor que 3000.
algorithms
strings
subsequences
Gilles 'SO- deja de ser malvado'
fuente
fuente
Respuestas:
Hay un algoritmo que lleva el nombre del algoritmo de Manacher, que es realmente rápido, un algoritmo de tiempo lineal.
Ver la referencia de Wikipedia
Postdata: Si está realmente familiarizado con el Algoritmo Z , encontrará que son similares.
Editar
Acabo de entender mal el significado del OP (pero no quiero eliminar la información del procedimiento. Es algo útil). Se refiere a la subsecuencia de palíndromo más larga de una cadena, por lo que la programación dinámica parece buena:
fuente
El algoritmo más rápido que se me ocurre es aplicar LCS de manera creativa. Puede resolver este problema en O (N ^ 2) tiempo y O (N ^ 2) espacio donde N es el tamaño de la cadena.
LCS (S, reverse (S)) le dará la subsecuencia palindrómica más grande, ya que la subsecuencia palindrómica más grande será la subsecuencia común más grande entre la cadena S y su reverso.
Por ejemplo,
S = "abcababac"
T = "cababacba" (reverso de S)
LCS (S, T) = "abababa"
fuente
El problema de encontrar LPS de una cadena se puede convertir en encontrar la subsecuencia común más larga de dos cadenas. En esto, una cadena será la original y la segunda será inversa a la cadena original.
El problema de la subsecuencia común más larga es como el problema de coincidencia de patrones, excepto que puede omitir caracteres en el texto. Además, el objetivo es devolver solo un partido, que es el mayor tiempo posible.
LCS se puede resolver enO(n2) utilizando recursividad y memorización.
Existe un algoritmo ligeramente más rápido descubierto por Masek y Paterson de complejidad temporalO(n2/lgn) . Enlace de papel: Masek y Paterson
Otros dos algoritmos presentados por Hirschberg para calcular LCS de dos cadenasA (Talla n ) y B (Talla m ) Basado en el supuesto de que los símbolos que pueden aparecer en estas cadenas provienen de algún alfabeto de tamañot (eso es realmente cierto en la mayoría de los casos). Entonces los símbolos se pueden almacenar en la memoria usandolog(t) bits, que caben en una palabra de memoria. dos símbolos se pueden comparar enO(1) hora. Número de diferentes en cadenaB se denota por s , que por supuesto es menor que ambos m y t .
Este requiereO(pn+nlgn) tiempo donde p es la longitud de LCS. Esto se usa cuando se espera que la longitud de LCS sea pequeña. Cuando resolvemos este problema usando la programación dinámica, encontramos que la mayoría de las entradas en la matriz son iguales, por lo que podemos usar la idea de la programación dinámica dispersa.
Este algoritmo requiereO(p(m+1−p)logn) hora. Esto es muy eficiente cuando la longitud de LCS está cerca dem , en ese caso estará cerca de O(nlgn) .
Los procedimientos y algoritmos detallados se explican en el artículo de Hirschberg .
Sohel Rahman propone otro buen algoritmo que se ejecuta enO(Rloglogn) tiempo, donde R es el número total de pares de posiciones ordenadas en las que las cadenas coinciden. No es aplicable cuandoR es el orden de O(n2) , pero hay muchos casos cuando R es el orden de n . Éste utiliza el concepto RMQ (consulta de rango máximo). Enlace de papel: Rahman
fuente
Probablemente me estoy perdiendo algo, porque me parece bastante trivial: intenta emparejar cada personaje con un personaje igual. Luego coloque el primer carácter de cada par en el lado izquierdo, el otro carácter en el lado derecho, y si quedan caracteres (es decir, caracteres no emparejados con otro), luego elija uno de ellos y póngalo en el medio.
fuente