Recientemente tuve una pregunta de la entrevista que fue algo como esto:¿Qué es un algoritmo típico para encontrar una cadena dentro de una cadena?
Dada una cadena grande (pajar), encontrar una subcadena (aguja)?
Estaba un poco perplejo para encontrar una solución decente.
¿Cuál es la mejor manera de abordar esto que no tiene una complejidad de tiempo deficiente?
Puede usar the Knuth-Morris-Pratt algorithm, que es O (n + m) donde n es la longitud de la cadena "pajar" ym es la longitud de la cadena de búsqueda.
No creo que haya nada mejor que mirar el pajar un personaje a la vez e intentar hacer coincidir con la aguja.
Esto tendrá complejidad de tiempo lineal (contra la longitud del pajar). Podría degradarse si la aguja está cerca de la misma longitud que el pajar y comparte un prefijo común y repetido.
El algoritmo de Knuth-Morris-Pratt @James McNellis menciona una mejora en esto que permite omitir algunos caracteres después de una coincidencia fallida. Todavía O (n), sin embargo. – Thilo
Recuerde que esta es una búsqueda, no una comparación. Considere buscar una cadena con muchos caracteres repetidos, en una cadena con muchos caracteres repetidos, y se dará cuenta de que su algoritmo es en realidad el peor caso de O (nm) donde n y m son cada uno la longitud de una cadena. El producto de dos variables no se clasifica como lineal (no es lo mismo que una constante desconocida por una variable), y ciertamente no es tan bueno como, por ejemplo, la suma de esas dos variables, que es alcanzable. – Steve314
@ Steve314: Eso es lo que quise decir con "degradar si la aguja está cerca de la misma longitud que el pajar y comparte un prefijo común y repetido" (sin embargo, el prefijo debería haber sido una subcadena). – Thilo
Este problema se trata en Hacking a Google Interview Practice Questions – Person A. Su solución de muestra:
bool hasSubstring(const char *str, const char *find) {
if (str[0] == '\0' && find[0] == '\0')
return true;
for(int i = 0; str[i] != '\0'; i++) {
bool foundNonMatch = false;
for(int j = 0; find[j] != '\0'; j++) {
if (str[i + j] != find[j]) {
foundNonMatch = true;
break;
}
}
if (!foundNonMatch)
return true;
}
return false;
}
sería bueno para devolver el índice de inicio del partido. En el escenario tradicional de pajar, ya sabes que la aguja está allí. algun lado. :-) – Thilo
¡Es un buen enlace! http://courses.csail.mit.edu/iap/interview/materials.php – Courtney85
Me gusta el Boyer-Moore algorithm. Es especialmente divertido implementarlo cuando tienes muchas agujas para encontrar en un pajar (por ejemplo, patrones probables de correo no deseado en un corpus de correo electrónico).
+1; Muy genial; No estaba familiarizado con este. Para agujas múltiples, también puede considerar el algoritmo Aho-Corasick. –
+1 Me enteré de Boyer-Moore hace muchos años en la revista "Computer Language" ... una joya (tanto el algoritmo como la revista) –
A algoritmo típico sería el siguiente, con índices de cadena que van de 0 a M-1.
Devuelve la posición de la coincidencia o -1 si no se encuentra.
foreach hpos in range 0 thru len(haystack)-len(needle):
found = true
foreach npos in range 0 thru len(needle):
if haystack[hpos+npos] != needle[npos]:
found = false
break
if found:
return hpos
return -1
Tiene un rendimiento razonable, ya que sólo comprueba el mayor número de caracteres en cada posición pajar, según sea necesario para descubrir que no hay posibilidad de un partido.
No es necesariamente el algoritmo más eficiente, pero si su entrevistador espera que sepa todos los algoritmos de alto rendimiento fuera de la cabeza, están siendo poco realistas (es decir, tontos). Un buen desarrollador conoce bien los conceptos básicos, y cómo averiguar las novedades donde sea necesario (por ejemplo, cuando hay un problema de rendimiento, no antes).
El rendimiento varía entre O (a) y O (ab) dependiendo de los datos reales en las cadenas, donde a y b son las longitudes de pajar y aguja, respectivamente.
Una posible mejora es almacenar, dentro del bucle npos, la primera ubicación mayor que hpos, donde el carácter coincide con el primer carácter de la aguja.
De esta manera puede omitir hpos en la siguiente iteración ya que sabe que no puede haber coincidencia antes de ese punto. Pero nuevamente, eso puede no ser necesario, dependiendo de sus requisitos de rendimiento. Debe calcular el equilibrio entre la velocidad y el mantenimiento usted mismo.
Uno de esos casos donde la capacidad de 'continuar' un bucle externo desde un interior el bucle sería increíble. –
@Mike: "goto se considera increíble"? ;-) –
Creo que también hay rotura/contine con una etiqueta. No es necesario ir a los extremos. – Thilo
El problema general es string searching; hay muchos algoritmos y enfoques dependiendo de la naturaleza de la aplicación.
Algunas estructuras de datos de índice avanzado también se usan en otras aplicaciones. Suffix trees se usan mucho en bioinformática; Aquí tiene un texto de referencia largo, y luego tiene muchas cadenas arbitrarias para las que desea encontrar todas las ocurrencias. Una vez que el índice (es decir, el árbol) se construye, encontrar patrones se puede hacer de manera bastante eficiente.
Para una respuesta de entrevista, creo que es mejor mostrar amplitud también. Conocer todos estos algoritmos diferentes y cuáles son los propósitos específicos a los que sirven mejor es probablemente mejor que conocer solo un algoritmo de memoria.
"Para una respuesta de entrevista, creo que es mejor mostrar amplitud también". No lo sé. ¿Se supone que debes saber esto de la parte superior de tu cabeza? En una situación de la vida real, buscaría el algoritmo en Internet. En una entrevista, esperaría que alguien presentara una implementación como Brian o paxdiablo show, y poder explicar cuándo funcionarían mal. – Thilo
Tenga en cuenta que mi experiencia es académica; hacemos una gran cantidad de lecturas de los artículos de la encuesta. Supongo que la gente esperaría que los candidatos supieran * ACERCA * de estos fuera de lo común, al menos hasta el nivel de detalle que se muestra en mi publicación (es decir, no mucho). Tienes razón, los detalles de los algoritmos se pueden buscar en la red, pero necesitan saber * SOBRE * ellos, para que sepan qué buscar y que exista. Además, supongo que depende del tipo de puesto para el que estés entrevistando. A veces simplemente necesitan que se hagan las cosas. Otras veces necesitan personas que sepan lo que sucede realmente allí afuera. – polygenelubricants
Otro ejemplo: se le pide al candidato que resuelva el TSP, sin revelar el nombre del problema. Un candidato rápidamente aparece con un algoritmo de fuerza bruta 'O (N!)', Señalando correctamente que es lento, etc. Otro reconoce inmediatamente que es TSP, lo que eso significa en términos de NP-completitud, qué enfoques se han intentado, existencia de algoritmos de aproximación inexactos pero buenos (incluso sin conocer sus detalles), etc. Creo que las personas estarían de acuerdo en que el segundo candidato es mejor que el primero, al menos para ciertos puestos. – polygenelubricants
Aquí hay un presentation de unos pocos algoritmos (desvergonzadamente vinculados de la Universidad de Humboldt). contiene algunos buenos algoritmos como Boyer More y Z-box.
Utilicé el algoritmo Z-Box, encontré que funcionaba bien y era más eficiente que Boyer-More, pero necesita algo de tiempo para entenderlo.
la manera más fácil, creo que es "pajar" .Contiene ("aguja");) simplemente divertido, no lo tome en serio. Creo que ya tiene su respuesta.
Llegué a la mitad escribiendo una respuesta cuando vi esto, leí el artículo y me di cuenta de que era lo mismo. Nunca había oído hablar de eso antes, pero utilicé algo parecido para una máquina de estado de emparejamiento de patrón binario en '94. Oh bien. –