A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Fast Algorithm for Finding a Maximal Common Subsequence of Multiple Strings Um algoritmo rápido para encontrar uma subsequência comum máxima de múltiplas strings

Miyuji HIROTA, Yoshifumi SAKAI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Para qualquer m cordas de comprimento total n, propomos um O(mn log n)-tempo, O(n)-espaço algoritmo que encontra uma subsequência comum máxima de todas as strings, no sentido de que a inserção de qualquer caractere nela não produz mais uma subsequência comum delas. Essa subsequência comum poderia ser tratada como uma indicação de uma estrutura comum não trivial que poderíamos encontrar nas strings, uma vez que é NP-difícil encontrar qualquer subsequência comum mais longa das strings.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.9 pp.1191-1194
Data de publicação
2023/09/01
Publicitada
2023/03/06
ISSN online
1745-1337
DOI
10.1587/transfun.2022DML0002
Tipo de Manuscrito
Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Categoria
Algoritmos e estruturas de dados

autores

Miyuji HIROTA
  Tohoku University
Yoshifumi SAKAI
  Tohoku University

Palavra-chave