Dec 9, 2009

Hallar la primera subcadena común mas larga en Python(find the first longest common substring)

Lo que quiero presentar aquí es un ejemplo de como encontrar la primera subcadena común mas larga en Python.

Mientras desarrollaba Sushi, huh? se me dio la necesidad de resolver este problema, pero pasa que después de buscar mucho, no encontré código para hacer esto y Python no trae una función para resolver este tipo de situaciones, así que después de poner a trabajar un poco el cerebro termine armando una función para hallar la LCS.

Actualización: Esta fue mi primera implementación del algoritmo LCS, lo realice por mero hobby, como un ejercicio mental, y como tal tiene algunos cuantos errores. Pueden ver la nueva versión de este algoritmo en mi nuevo post.

La idea es comenzar comparando la primera letra de una cadena "a" con la ultima letra de la cadena "b", e ir corriendo "a" hacia la derecha y "b" hacia la izquierda cada vez hasta terminar comparando la ultima letra de una cadena "a" con la primera letra de la cadena "b", para finalmente por comparación encontrar aquella cadena en común que sea mas larga.




































#!/usr/bin/env python
# -*- coding: utf-8 -*-
# lcs.py Finding the first longest common substring in Python.
# Copyright (C) 2008  Gonzalo Exequiel Pedone
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with This program.  If not, see .
#
# Email   : hipersayan DOT x AT gmail DOT com
# Web-Site: http://hipersayanx.blogspot.com/

def lcs(a='', b=''):
    comp_a = []
    comp_b = []

    i_list = list(range(len(a)))
    i_list.reverse()

    # Empezamos leyendo la ultima letra de "a" y luego desplazamos "a" hacia la
    # derecha cada vez, hasta terminar en la primera letra de "a".
    # Cada uno de los resultados lo guardamos dentro de la lista "comp_a".
    for i in i_list:
        comp_a += [a[i:][: len(b)]]

    for i in i_list:
        comp_a += [a[: i][: len(b)]]

    # Vea el ejemplo para mas claridad
    # for s in comp_a:
    #     print(s)

    j_list = range(len(b))

    # Empezamos leyendo la primera letra de "b" y luego desplazamos "b" hacia la
    # izquierda cada vez, hasta terminar en la ultima letra de "b".
    # Cada uno de los resultados lo guardamos dentro de la lista "comp_b".
    for j in j_list:
        comp_b += [b[: j][: len(a)]]

    for j in j_list:
        comp_b += [b[j:][: len(a)]]

    # Vea el ejemplo para mas claridad
    # for s in comp_b:
    #     print(s)

    # Luego aislamos solo aquellas cadenas que vamos a comparar.
    diff_a = len(comp_a) - len(set(comp_a))
    diff_b = len(comp_b) - len(set(comp_b))

    if diff_a == 0:
        if diff_b != 0:
            for i in comp_b:
                if comp_b.count(i) != 1:
                    for j in range(diff_b):
                        comp_b.remove(i)

                break

        a_index = comp_a.index(a)
        comp_a = comp_a[: a_index] + (diff_b) * [a] + comp_a[a_index:]
    else:
        if diff_b == 0:
            for i in comp_a:
                if comp_a.count(i) != 1:
                    for j in range(diff_a):
                        comp_a.remove(i)

                    break

            b_index = comp_b.index(b)
            comp_b = comp_b[: b_index] + (diff_a) * [b] + comp_b[b_index:]

    comp_a = comp_a[: len(comp_a) - 1]
    comp_b = comp_b[1:]

    # Vea el ejemplo para mas claridad
    # for s in range(len(comp_a)):
    #     print('a = ' + comp_a[s])
    #     print('b = ' + comp_b[s])

    the_longest = ''
    comp_string = ''

    # Luego comparamos letra por letra y vamos armando una palabra mientras
    # estas sean iguales, y cuando esta palabra sea la mas larga la guardamos en
    # "the_longest" y empezamos con una nueva "comp_string".
    for i in range(len(comp_a)):
        for j in range(len(comp_a[i])):
            if comp_a[i][j] == comp_b[i][j]:
                comp_string += comp_a[i][j]
            else:
                if len(comp_string) > len(the_longest):
                    the_longest = comp_string

                comp_string = comp_a[i][j]

    return the_longest[1:]

a = 'Andrea siempre llevaba a su gato negro a todos los lugares a donde viajaba.'
b = 'A ella le gustaba su gato negro porque era muy traviezo y jugueton.'

print(a)
print(b)
print()
print('Que llevaba siempre Andrea?')
print()
print(lcs(a, b))

2 comments:

  1. Vi que te gustó el plugin de Gimp. Si sigues lo que dice este artículo puedes mejorar el aspecto de tu código python:

    http://blogdezeka.blogspot.com/2010/06/como-usar-sintax-highlighter-en-blooger.html

    Por otra parte, en el Blog de Cole te señala como switchear hacia un look que vaya más acorde con el color negro de tu blog.

    Saludos

    ReplyDelete
  2. Muchas gracias José, la verdad es que no he tenido mucho tiempo como para mantener el blog, estoy con la idea de empezar un nuevo proyecto y haciendo algunas pruebas, y por eso esta un poquito descuidado :P, la verdad que mantener un blog no es nada facil.
    Pero dentro de poco voy a ver si publico algun a entrada mas.

    ReplyDelete