elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Usando Git para manipular el directorio de trabajo, el índice y commits (segunda parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  ¿Cual es el algoritmo más eficiente para sacar la subcadena común mayor?
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: ¿Cual es el algoritmo más eficiente para sacar la subcadena común mayor?  (Leído 752 veces)
pran_krr

Desconectado Desconectado

Mensajes: 2


Ver Perfil
¿Cual es el algoritmo más eficiente para sacar la subcadena común mayor?
« 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.


En línea

Serapis
Colaborador
***
Conectado Conectado

Mensajes: 2.769


Ver Perfil
Re: ¿Cual es el algoritmo más eficiente para sacar la subcadena común mayor?
« Respuesta #1 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.


En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines