2011/8/2 Stanislaw Pusep <[email protected]> > Bruno, tanto LCS quanto LCSS fazem comparação de 2 em 2, certo? Ao menos, > pela implementação "naive", que monta uma matriz... Já pelo conceito > do Generalised suffix tree, daria para "comparar" 3 ou mais, não?
LCS e LCSS são problemas "genéricos", não estão limitados a quantidade de strings. A solução que utiliza uma matriz s1*s2, é uma abordagem por programação dinâmica e não tenho certeza se a generalização para mais de 2 strings é de fato trivial. Mas utilizando estruturas de dados melhores, como por exemplo a árvore se sufixo, com certeza é generalizado para n strings. (Mas a complexidade acaba sendo praticamente a mesma, produtório dos tamanhos das strings) [ ]'s -- Bruno C. Buss http://brunobuss.wordpress.com/ http://www.dcc.ufrj.br/~brunobuss/
=begin disclaimer Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ SaoPaulo-pm mailing list: [email protected] L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> =end disclaimer
