algorithm - problems - Compruebe si la cadena dada puede ser creada por un conjunto de caracteres recortados del artículo de la revista

dynamic programming problems

Question

"Observe que cuando elimina un carácter de una revista, también se elimina el carácter en el reverso de la página. Dé un algoritmo para determinar si puede generar una cadena determinada pegando recortes de una revista determinada. Suponga que usted es dada una función que identificará el carácter y su posición en el reverso de la página para cualquier posición de carácter dada ".

¿Cómo puedo hacerlo?

Puedo hacer una poda inicial, de modo que si un personaje necesario solo tiene una forma de ser recogido, se toma inicialmente antes de convertir el subproblema de la técnica dinámica, pero ¿qué ocurre después de esta poda inicial?

¿Cuál es la complejidad del tiempo y el espacio?

Answer 1

Como sugirió @LiKao, esto se puede resolver utilizando el flujo máximo. Para construir la red, creamos dos "capas" de vértices: una con todos los caracteres distintos en la cadena de entrada y otra con cada posición en la página. Haga una arista con capacidad 1 de un personaje a una posición si esa posición tiene ese carácter en un lado. Haga bordes de capacidad 1 desde cada posición al sumidero, y haga bordes desde la fuente a cada carácter con capacidad igual a la multiplicidad de ese carácter en la cadena de entrada.

Por ejemplo, digamos que estamos buscando la palabra "FOO" en una página con cuatro posiciones:

pos    1 2 3 4
front  F C O Z
back   O O K Z

Luego generamos la siguiente red, ignorando la posición 4 ya que no proporciona ninguno de los caracteres requeridos.

Ahora, solo necesitamos determinar si hay un flujo desde la fuente hasta el sumidero de length("FOO") = 3 o más.

Answer 2

Puede utilizar la programación dinámica directamente.

Nos dan la cadena s con n letras. Nos dan un conjunto de piezas P = {p_1, ..., p_k}. Cada pieza tiene una letra en la parte delantera p_i.f y una en la parte posterior p_i.b.

Denote con f (j, p) la función que devuelve true si es posible crear la subcadena s_1 ... s_j usando piezas en p / subseteq P, y false en caso contrario.

Se mantiene la siguiente recurrencia: f (n, P) = f (n-1, P-p_1) | f (n-1, P-p_2) | ... | f (n-1, P-p_k)

En un lenguaje sencillo, la viabilidad de s utilizando todas las piezas en P depende de la factibilidad de la subcadena s_1 ... s_n-1 dado una pieza menos, e intentamos eliminar todas las piezas posibles (por supuesto, en la práctica no tenemos que eliminarlas). todas las piezas una por una; solo necesitamos eliminar aquellas piezas para las que p_i.f == s_n || p_i.b == s_n).

La condición inicial es que f (1, P-p_1) = f (1, P-p2) = ... = verdadero, asumiendo que ya hemos verificado a priori (en tiempo lineal) que hay suficientes letras en P Para cubrir todas las letras en el s.