IEICE TRANSACTIONS on Fundamentals
A Fast Algorithm for Finding a Maximal Common Subsequence of Multiple Strings
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.9 pp.1191-1194
- Publication Date
- 2023/09/01
- Publicized
- 2023/03/06
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2022DML0002
- Type of Manuscript
- Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Algorithms and Data Structures
Authors
Miyuji HIROTA
Tohoku University
Yoshifumi SAKAI
Tohoku University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
