Agrega la menor cantidad de caracteres para hacer un palíndromo

Solución:

1. Revertir la cuerda
2. Use un Knuth-Morris-Pratt modificado para encontrar la última coincidencia (la modificación más simple sería simplemente agregar la cadena original a la cadena revertida e ignorar las coincidencias después de len (cadena).
3. Agregue el resto incomparable de la cadena revertida al original.

1 y 3 son obviamente lineales y 2 es lineal porque Knuth-Morris-Pratt lo es.

Si solo se permite agregar

Una solución Scala:

def isPalindrome(s: String) = s.view.reverse == s.view

def makePalindrome(s: String) = 
  s + s.take((0 to s.length).find(i => isPalindrome(s.substring(i))).get).reverse

Si tiene permitido insertar caracteres en cualquier lugar

Cada palíndromo puede verse como un conjunto de pares de letras anidados.

a  n  n  a         b  o  b
|  |  |  |         |  *  |
|   --   |         |     |
---------           -----

Si la longitud del palíndromo n es par, tendremos n / 2 pares. Si es impar, tendremos n / 2 pares completos y una sola letra en el medio (llamémoslo un par degenerado).

Representémoslos por pares de índices de cadena: el índice izquierdo contado desde el extremo izquierdo de la cadena y el índice derecho contado desde el extremo derecho de la cadena, ambos extremos comenzando con el índice 0.

Ahora escribamos pares empezando desde el exterior hacia el interior. Entonces en nuestro ejemplo:

anna: (0, 0) (1, 1)
bob: (0, 0) (1, 1)

Para hacer de cualquier cadena un palíndromo, iremos desde ambos extremos de la cadena un carácter a la vez, y con cada paso, eventualmente agregaremos un carácter para producir un par correcto de caracteres idénticos.

Ejemplo: suponga que la palabra de entrada es “blob”

1. El par (0, 0) es (b, b) ok, no hay nada que hacer, este par está bien. Aumentemos el contador.
2. El par (1, 1) es (l, o). No coincide. Así que agreguemos “o” en la posición 1 desde la izquierda. Ahora nuestra palabra se convirtió en “bolob”.
3. Emparejar (2, 2). No necesitamos mirar incluso a los caracteres, porque estamos apuntando al mismo índice en la cadena. Hecho.

Espere un momento, pero tenemos un problema aquí: en el punto 2. elegimos arbitrariamente agregar un carácter a la izquierda. Pero también podríamos agregar un carácter “l” a la derecha. Eso produciría “blolb”, también un palíndromo válido. Entonces, ¿importa? Desafortunadamente, lo hace porque la elección en los pasos anteriores puede afectar la cantidad de pares que tendremos que arreglar y, por lo tanto, la cantidad de caracteres que tendremos que agregar en los pasos futuros.

Algoritmo sencillo: busca todas las posibilidades. Eso nos daría un algoritmo O (2 ^ n). Mejor algoritmo: utilice el enfoque de programación dinámica y reduzca el espacio de búsqueda.

Para simplificar las cosas, ahora desacoplamos la inserción de nuevos caracteres de simplemente encontrar la secuencia correcta de pares anidados (de afuera hacia adentro) y arreglar su alineación más tarde. Entonces, para la palabra “gota” tenemos las siguientes posibilidades, ambas terminando con un par degenerado:

(0, 0) (1, 2)
(0, 0) (2, 1)

Cuantos más pares de este tipo encontremos, menos caracteres tendremos que agregar para arreglar la cadena original. Cada par completo encontrado nos da dos caracteres que podemos reutilizar. Cada par degenerado nos da un carácter para reutilizar.

El bucle principal del algoritmo evaluará iterativamente las secuencias de pares de tal manera que en el paso 1 se encuentren todas las secuencias de pares válidas de longitud 1. El siguiente paso evaluará secuencias de longitud 2, las terceras secuencias de longitud 3, etc. Cuando en algún paso no encontramos posibilidades, esto significa que el paso anterior contiene la solución con el mayor número de pares.

Después de cada paso, eliminaremos las secuencias pareto-subóptimas. Una secuencia es subóptima en comparación con otra secuencia de la misma longitud, si su último par es dominado por el último par de la otra secuencia. Por ejemplo, la secuencia (0, 0) (1, 3) es peor que (0, 0) (1, 2). Este último nos da más espacio para encontrar pares anidados y tenemos la garantía de encontrar al menos todos los pares que encontraríamos para el primero. Sin embargo, la secuencia (0, 0) (1, 2) no es ni peor ni mejor que (0, 0) (2, 1). El único detalle menor con el que debemos tener cuidado es que una secuencia que termina con un par degenerado siempre es peor que una secuencia que termina con un par completo.

Después de juntarlo todo:

def makePalindrome(str: String): String = {

  /** Finds the pareto-minimum subset of a set of points (here pair of indices).
    * Could be done in linear time, without sorting, but O(n log n) is not that bad ;) */
  def paretoMin(points: Iterable[(Int, Int)]): List[(Int, Int)] = {
    val sorted = points.toSeq.sortBy(identity)
    (List.empty[(Int, Int)] /: sorted) { (result, e) =>
      if (result.isEmpty || e._2 <= result.head._2)
        e :: result
      else
        result
    }
  }

  /** Find all pairs directly nested within a given pair.
    * For performance reasons tries to not include suboptimal pairs (pairs nested in any of the pairs also in the result)
    * although it wouldn't break anything as prune takes care of this. */
  def pairs(left: Int, right: Int): Iterable[(Int, Int)] = {
    val builder = List.newBuilder[(Int, Int)]
    var rightMax = str.length
    for (i <- left until (str.length - right)) {
      rightMax = math.min(str.length - left, rightMax)
      val subPairs =
        for (j <- right until rightMax if str(i) == str(str.length - j - 1)) yield (i, j)

      subPairs.headOption match {
        case Some((a, b)) => rightMax = b; builder += ((a, b))
        case None =>
      }
    }

    builder.result()
  }

  /** Builds sequences of size n+1 from sequence of size n */
  def extend(path: List[(Int, Int)]): Iterable[List[(Int, Int)]] =
    for (p <- pairs(path.head._1 + 1, path.head._2 + 1)) yield p :: path

  /** Whether full or degenerated. Full-pairs save us 2 characters, degenerated save us only 1. */
  def isFullPair(pair: (Int, Int)) =
    pair._1 + pair._2 < str.length - 1

  /** Removes pareto-suboptimal sequences */
  def prune(sequences: List[List[(Int, Int)]]): List[List[(Int, Int)]] = {
    val allowedHeads = paretoMin(sequences.map(_.head)).toSet
    val containsFullPair = allowedHeads.exists(isFullPair)
    sequences.filter(s => allowedHeads.contains(s.head) && (isFullPair(s.head) || !containsFullPair))
  }

  /** Dynamic-Programming step */
  @tailrec
  def search(sequences: List[List[(Int, Int)]]): List[List[(Int, Int)]] = {
    val nextStage = prune(sequences.flatMap(extend))
    nextStage match {
      case List() => sequences
      case x => search(nextStage)
    }
  }

  /** Converts a sequence of nested pairs to a palindrome */
  def sequenceToString(sequence: List[(Int, Int)]): String = {
    val lStr = str
    val rStr = str.reverse

    val half =
      (for (List(start, end) <- sequence.reverse.sliding(2)) yield
        lStr.substring(start._1 + 1, end._1) + rStr.substring(start._2 + 1, end._2) + lStr(end._1)).mkString

    if (isFullPair(sequence.head))
      half + half.reverse
    else
      half + half.reverse.substring(1)
  }

  sequenceToString(search(List(List((-1, -1)))).head)
}

Nota: El código no enumera todos los palíndromos, pero solo da un ejemplo, y se garantiza que tiene la longitud mínima. Por lo general, hay más palíndromos posibles con la misma longitud mínima (O (2 ^ n) en el peor de los casos, por lo que probablemente no desee enumerarlos todos).

Creo que la respuesta de @ Chronical es incorrecta, como parece ser para en el mejor de los casos, no peor de los casos que se utiliza para calcular la complejidad de Big-O. Doy la bienvenida a la prueba, pero la “solución” en realidad no describe una respuesta válida.

KMP encuentra una subcadena coincidente en O(n * 2k) tiempo, donde n es la longitud de la cadena de entrada, y k subcadena que estamos buscando, pero no en O(n) el tiempo te diga lo que el mas largo palíndromo en la cadena de entrada es.

Para resolver este problema, necesitamos encontrar el palíndromo más largo al final de la cuerda. Si este sufijo palíndromo más largo es de longitud x, el número mínimo de caracteres para agregar es n - x. Por ejemplo, la cuerda aabaLa subcadena de sufijo más larga es aba de longitud 3, entonces nuestra respuesta es 1. El algoritmo para averiguar si una cuerda es un palíndromo toma O(n) tiempo, ya sea usando KMP o el algoritmo más eficiente y simple (O(n/2)):

Tome dos punteros, uno en el primer carácter y otro en el último carácter

Compare los caracteres en los punteros, si son iguales, mueva cada puntero hacia adentro, de lo contrario regrese false

Cuando los punteros apuntan al mismo índice (longitud de cadena impar), o se han superpuesto (longitud de cadena par), devuelve true

Usando el algoritmo simple, partimos de la cadena completa y verificamos si es un palíndromo. Si es así, volvemos 0, y si no, revisamos la cadena string[1...end], string[2...end] hasta que hayamos llegado a un solo carácter y volvamos n - 1. Esto da como resultado un tiempo de ejecución de O(n^2).

Dividiendo el algoritmo KMP en

Mesa de construcción

Buscar el sufijo palíndromo más largo

Construir la mesa requiere O(n) tiempo, y luego cada verificación de “eres un palíndromo” para cada subcadena de string[0...end], string[1...end], ..., string[end - 2...end] cada uno toma O(n) tiempo. k en este caso es el mismo factor de n que toma el algoritmo simple para verificar cada subcadena, porque comienza como k = n, luego pasa por k = n - 1, k = n - 2… al igual que lo hizo el algoritmo simple.

TL; DR:

KMP puede decirle si una cuerda es un palíndromo en O(n) tiempo, pero eso proporciona una respuesta a la pregunta, porque debe verificar si todas las subcadenas string[0...end], string[1...end], ..., string[end - 2...end] son palíndromos, lo que da como resultado el mismo tiempo de ejecución (pero en realidad peor) que un algoritmo simple de verificación de palíndromos.

---

---

Utiliza Nuestro Buscador