Cómo resolver el problema ‘Eliminar la cadena’ (PSTRING) en SPOJ

No he resuelto personalmente este problema y no estoy seguro de si será aceptado en un servidor, pero aquí hay algunas ideas.

Suponga que tiene una función F (x1, y1) que indica cuántos símbolos se eliminaron de la subcadena [0, x1] de X (1) de modo que y1 es la longitud de la subcadena común del sufijo de (1) y el prefijo de Y.

Básicamente, x1 es el número de símbolos procesados ​​desde X, X [0, x1] es una cadena procesada.
y1 es la longitud de la subcadena común del prefijo Y y el sufijo de X [0, x1]

Ahora, digamos que procesamos los símbolos x1 de X. Cuando obtenemos el símbolo x1 + 1, hay dos opciones: omitir el símbolo (eliminarlo) o no omitirlo.
El símbolo de omisión conducirá a una eliminación adicional que debemos contar, no omitir provocará cambios en la cadena común.

F (x1 + 1, y1) = min (F (x1, y1) +1 / * simplemente elimine el símbolo en la posición x1 + 1, la parte común no se cambiará * /, F (x1, y2));

y2 es algo que necesitarías calcular. Sabes que solía ser una cadena común de longitud y1, ahora obtienes el carácter adicional X [x1 + 1]. Aquí puede usar una técnica similar a KMP con la función de prefijo precompilación para descubrir el nuevo valor de y2.

El resultado será min (foreach i de 0 a Y.length () – 1 F (X.length (), i)).
La cadena X está completamente procesada y la longitud de la parte común está entre 0 e Y.length () – 1.

Suponiendo que conoces el algoritmo KMP o Z

Cada vez que obtenga una combinación perfecta de Y en X, inserte este índice en una matriz. Luego usamos un enfoque codicioso. Recorre linealmente la matriz obtenida.

prev = 0;

Si obtienes un valor tal que

A [idx] -a [prev]> strlen (Y),

luego responda ++, prev = idx.

Al final, para evitar un error, marque y agregue 1 a la respuesta.

¿Por qué funciona codicioso ? Es porque no podemos dejar de cubrir ningún índice en la matriz obtenida. Para cubrir todos los valores en A, tenemos que agruparlos en conjuntos disjuntos donde cada conjunto tiene algunos índices consecutivos de A. A ya estaba ordenado cuando lo creamos (debido a la función transversal transversal de falla). En cada uno de estos conjuntos, el valor del extremo derecho-valor del extremo izquierdo debe ser menor o igual que strlen (Y) para garantizar la superposición entre todas las subcadenas correspondientes a estos valores (estos valores son puntos finales de la subcadena siempre que haya una coincidencia perfecta). Por lo tanto, eliminar solo 1 carácter de la región superpuesta cubrirá todo el conjunto.

Parece que otras respuestas usaron DP. Quizás codicioso fallará en algún caso de prueba después de todo. Avíseme si codicioso funciona o no, de cualquier manera. Es más fácil de implementar, así que espero que pase.

Este problema se puede resolver con un algoritmo de programación dinámico y utilizando la función de falla del algoritmo KMP.

A continuación se detalla un esquema aproximado.
1. Calcule la función de falla para Y.
2. A medida que escanea X de izquierda a derecha, mantiene el sufijo más grande (de X visto hasta ahora) que también es un prefijo de Y. A medida que elige agregar o ignorar el carácter X actual, este sufijo más grande cambia. Debe hacer sus elecciones de tal manera que el sufijo más grande nunca esté lleno.

Esto nos da un tiempo de ejecución de O (| X | * | Y |), con un requisito de memoria de O (| Y |). No sé si hay un mejor algoritmo.