Longest Common Substring - troca de ideias para algoritmos

[thoga31]

Boas, pessoal!

Estou a tentar aprofundar o meu conhecimento em algoritmia e cruzei-me com o famoso problema LCS.

Implementei uma solução que recorre a uma adaptação do Algoritmo de Wagner-Fischer para determinar qual o comprimento da maior substring comum. Contudo, a complexidade é O(m.n), o que no pior caso se traduz em O(n²). Após pesquisa, encontrei referências à possível existência de algoritmos com melhor complexidade.

Venho, pois, ter convosco para vos lançar o tópico, debater algoritmos e saciar a minha curiosidade: conheceis algoritmos com melhor complexidade para resolver este problema? Se sim, quais e com que complexidade?

Obrigado desde já.

Cumprimentos.

[Warrior]

Consegues resolver em O(m+n) com uma árvore de sufixos (suffix tree). Julgo que também deve ser possível com o vector de sufixos (suffix array), mas tinha que pensar melhor. Se calhar tens que meter um log(m) aí no meio.

[thoga31]

Obrigado @Warrior, na altura acabei por me cruzar com os suffix arrays e implementei uma solução com base nesse algoritmo. Também encontrei as suffix trees, mas para ser honesto, não me senti com coragem de as implementar 😄