|
Título: ¿Cual es el algoritmo más eficiente para sacar la subcadena común mayor? Publicado por: pran_krr en 17 Noviembre 2019, 13:27 pm El problema que tengo es que dadas dos listas de ints, tengo que hallar la mayor subcadena común mayor. Por ejemplo, si tengo Cad1 = [1,2,3,4,5,6,7,8,9] y Cad2 = [1,2,35,1,2,3,4,2,5,8,5], el resultado tendría que ser [1,2,3,4]. Hasta el momento he visto que usando el algoritmo de búsqueda de Boyer-Moore es con el que mejor lo podría hacer pero no se si existe algún otro algoritmo mejor para la ocasión. Gracias por adelantado : :D.
Título: Re: ¿Cual es el algoritmo más eficiente para sacar la subcadena común mayor? Publicado por: Serapis en 27 Noviembre 2019, 16:45 pm El 'algoritmo KMP' (de Knuth, Morris y Pratt) es un algoritmo para buscar subacadenas completas, como en tu caso la búsqueda es parcial... puede ser readaptado para dicha situación.
https://es.wikipedia.org/wiki/Algoritmo_Knuth-Morris-Pratt Hace ya como 8-9 años edité el algoritmo (en wikipedia) para expresar claramente el funcionamiento (era un galimatías incomprensible) y poner ejemplos más explícitos y paso a paso así como el pseudocódigo del mismo (había ineficientes implementaciones en varios lenguajes). ...fíjate que el algoritmo se compone de dos partes, en la primera se precomputa una tabla de saltos, que acelerarán las búsqueda. Puede ser aún más aficiente si se conoce previamente que 'SIEMPRE' se darán ciertas condiciones, que si ha de ser universal (por ejemplo, saber que la subcadena a buscar siempre será máyor de x caracteres y si es menor se rechaza). Aunque igualmente puedes readaptar el algoritmo de Boyer-Moore para el mismo propósito. Claro la cosa está en si implementas el algoritmo o simplemente lo utilizas desde una librería, en cuyo caso no ha lugar a optimización, si no simples llamadas en un bucle. |