Lalit Kundu hace un buen trabajo explicando lo que hay que hacer. Solo me ampliaré en eso. Se nos da un conjunto de caracteres (llamado alfabeto ) y un conjunto de palabras (que son grupos de caracteres).
Dadas dos palabras de este conjunto [matemática] w_i [/ matemática] y [matemática] w_j [/ matemática], y un orden entre ellas, siempre podemos encontrar una ordenación entre los diferentes caracteres en la misma posición de índice. Por lo tanto, dado [math] w_i <w_j [/ math], si este par difiere en los caracteres [math] c_i [/ math] y [math] c_j [/ math], entonces el orden [math] c_i <c_j [/ se puede decir que math] forma un par ordenado válido [math] (c_i, c_j) [/ math].
Dados todos estos pares ordenados, nos quedan esencialmente dos problemas:
- ¿Son factibles los problemas NP-difíciles?
- ¿Por qué es necesario un relleno de palabra no utilizado al comienzo del espacio de almacenamiento dinámico asignado?
- ¿Por qué deberíamos instanciar una matriz en una línea diferente?
- ¿Hay algún tutorial de algoritmos y estructuras de datos donde aprendas a través de los juegos?
- ¿Qué viene después de aprender la biblioteca de plantillas estándar, las estructuras de datos y los algoritmos en C ++?
- ¿Cómo almacenamos estos pares ordenados de manera eficiente?
- ¿Cómo encontramos un orden válido entre todos los caracteres que forman cada uno de los pares ordenados (una vez que hayamos almacenado bien estos pares ordenados)?
El primer problema se resuelve fácilmente con un gráfico de dependencia. Lo haces incluyendo una arista dirigida desde [math] c_i [/ math] a [math] c_j [/ math] para el par ordenado [math] (c_i, c_j) [/ math]. En esta etapa, si encuentra dos pares ordenados en conflicto (por ejemplo, [math] (a, b) [/ math] y [math] (b, a) [/ math]), se puede decir que un pedido válido no puede existen entre este par de personajes. El orden entre ellos es, por lo tanto, ambiguo y no puede incluirse de manera confiable en nuestro resultado. En este punto, puede elegir mantener cualquiera de los bordes (suponga que uno de los pares de pedidos es válido mientras que el otro no lo es) o eliminar ambos de su gráfico.
El segundo problema se resuelve ordenando topológicamente el gráfico que construyó para resolver su primer problema. El orden topológico le dará el orden correcto de los caracteres en su alfabeto dado que el gráfico de dependencia que construyó era válido.
