Maximal common subsequence algorithms
| Autor: | Yoshifumi Sakai |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
TheoryofComputation_MISCELLANEOUS
000 Computer science knowledge general works General Computer Science 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Longest common subsequence problem Character (mathematics) 010201 computation theory & mathematics Computer Science Subsequence 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Algorithm Mathematics |
| Zdroj: | Theoretical Computer Science. 793:132-139 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2019.06.020 |
| Popis: | A common subsequence of two strings is maximal, if inserting any character into the subsequence can no longer yield a common subsequence of the two strings. The present article proposes a (sub)linearithmic-time, linear-space algorithm for finding a maximal common subsequence of two strings and also proposes a linear-time algorithm for determining if a common subsequence of two strings is maximal. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect