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
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.
Miyuji HIROTA
Tohoku University
Yoshifumi SAKAI
Tohoku University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Miyuji HIROTA, Yoshifumi SAKAI, "A Fast Algorithm for Finding a Maximal Common Subsequence of Multiple Strings" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 9, pp. 1191-1194, September 2023, doi: 10.1587/transfun.2022DML0002.
Abstract: For any m strings of total length n, we propose an O(mn log n)-time, O(n)-space algorithm that finds a maximal common subsequence of all the strings, in the sense that inserting any character in it no longer yields a common subsequence of them. Such a common subsequence could be treated as indicating a nontrivial common structure we could find in the strings since it is NP-hard to find any longest common subsequence of the strings.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022DML0002/_p
Copiar
@ARTICLE{e106-a_9_1191,
author={Miyuji HIROTA, Yoshifumi SAKAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Fast Algorithm for Finding a Maximal Common Subsequence of Multiple Strings},
year={2023},
volume={E106-A},
number={9},
pages={1191-1194},
abstract={For any m strings of total length n, we propose an O(mn log n)-time, O(n)-space algorithm that finds a maximal common subsequence of all the strings, in the sense that inserting any character in it no longer yields a common subsequence of them. Such a common subsequence could be treated as indicating a nontrivial common structure we could find in the strings since it is NP-hard to find any longest common subsequence of the strings.},
keywords={},
doi={10.1587/transfun.2022DML0002},
ISSN={1745-1337},
month={September},}
Copiar
TY - JOUR
TI - A Fast Algorithm for Finding a Maximal Common Subsequence of Multiple Strings
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1191
EP - 1194
AU - Miyuji HIROTA
AU - Yoshifumi SAKAI
PY - 2023
DO - 10.1587/transfun.2022DML0002
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2023
AB - For any m strings of total length n, we propose an O(mn log n)-time, O(n)-space algorithm that finds a maximal common subsequence of all the strings, in the sense that inserting any character in it no longer yields a common subsequence of them. Such a common subsequence could be treated as indicating a nontrivial common structure we could find in the strings since it is NP-hard to find any longest common subsequence of the strings.
ER -