Graficar con palabras en los bordes.

Question

Estoy practicando la solución de problemas de programación. Aquí tengo algunos problemas:

Nos han dado un grafo dirigido $G$ $n\le 100$ nodos y $m\le 1000$ bordes, que son los bordes marcados (las etiquetas son también) con las palabras más corto de $1000$ personajes. Para una palabra dada $s$ ($|s|\le 10^5$) decidir si existe un camino (borde repeticiones están permitidos) $e_1,...,e_n$$G$, de tal manera que después de concatenar las palabras de los bordes $e_1,...,e_n$ (en este orden), llegamos a la palabra $s$.

Por ejemplo, $n=3, m=4$ y bordes: $1\xrightarrow{abc} 2, \ 2\xrightarrow{a} 1, \ 1\xrightarrow{aaa} 2, \ 2\xrightarrow{xyz} 3$, podemos crear la palabra $abcaaaaxyz$

Pero para $n=2, \ m=3$ y bordes: $1\xrightarrow{aa} 2, 2\xrightarrow{aa} 1, 1\xrightarrow{aa} 2$, no podemos crear la palabra $aaaaa$.

Yo estaba pensando acerca de este problema durante mucho tiempo y no sé cómo abordarlo. $G$ parece ser muy pequeño, pero cada recta solución de fuerza bruta será de curso muy lento creo que (la comparación de las palabras, recordando a los estados en la recursivo caminar a través de $G$). Realmente quiero saber cómo resolverlo. Alguien puede ayudar?

Answer 1

Una forma (subóptima) es mantener una matriz de$\le m\cdot maxlen =1000000$ bits, donde cada bit representa "La cadena hasta ahora puede coincidir con el carácter$i$ de la etiqueta de borde$j$" y actualizar Esta char por char de la entrada. Sin embargo, el tiempo de ejecución de$O(s\cdot m\cdot maxlen)$ puede prohibir esto para aplicaciones prácticas.

Los mejores métodos ubican todas las posiciones donde la cadena$j$ ocurre (completamente) en la entrada (en tiempo de ejecución$O(maxlen+s)$, no$O(maxlen\cdot s)$!) Y luego usan DP o, por ejemplo, una cola de prioridad con memoria$O(n\cdot maxlen)$ para el procesamiento final.

Answer 2

¿Qué tipo de fuerza bruta de las que están hablando? ¿Qué tipo de complejidad que esperabas? Es la siguiente demasiado lento para usted?

Algunos al azar enfoque: crear un gráfico de $G'$ $n\cdot s$ los nodos donde existe una arista entre el $(n_1,s_1)$ $(n_2,s_2)$ cuando se puede mover de $n_1$ $n_2$por el borde con una etiqueta $w$ tal que $s_2 = s_1 + w$. Luego ir a través de todos los bordes y coincidente con algunos de extensión de KMP para varios patrones de crear todas las $m\cdot s$ bordes. Por último, compruebe si existe un camino desde el principio hasta el final.

Edit: Solo una aclaración, no espero que este código exactamente como lo describe, porque es probable que se ejecute fuera de la memoria. En lugar de crear el gráfico off-line, sólo la accesibilidad, que es un $\mathtt{bool}$ matriz de tamaño $n \cdot s$ describir si el nodo es accesible (de hecho, las palabras son más cortas de 1000 caracteres, por lo $n \cdot 1001$ debería ser suficiente). El gráfico debe ser creado en línea, con $m$ paralelo copias de KMP ser evaluados perezosamente, que es lo que necesita para mantener el $m$ estados para cada algoritmo y mover de uno en uno cada vez que se proceda a la siguiente carácter. Cuando KMP para la palabra $w$ de borde de $(n_1,n_2)$ le dice que no es un partido, y hay una accesibilidad conjunto de bits de $(n_1,s_1)$ donde $s_1$ es la posición actual, luego se establece la accesibilidad de bits de $(n_2,s_1+|w|)$.

Espero que esta ayuda ;-)