|
| | | | |
| | | |
| Stat |
Members: 3644
Articles: 2'499'343
Articles rated: 2609
16 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A Practical O(Rloglog n+n) time Algorithm for Computing the Longest Common Subsequence | | Daxin Zhu
; Lei Wang
; Yingjie Wu
; Xiaodong Wang
; | | Date: |
23 Aug 2015 | | Abstract: | In this paper, we revisit the much studied LCS problem for two given
sequences. Based on the algorithm of Iliopoulos and Rahman for solving the LCS
problem, we have suggested 3 new improved algorithms. We first reformulate the
problem in a very succinct form. The problem LCS is abstracted to an abstract
data type DS on an ordered positive integer set with a special operation
Update(S,x). For the two input sequences X and Y of equal length n, the first
improved algorithm uses a van Emde Boas tree for DS and its time and space
complexities are O(Rloglog n+n) and O(R), where R is the number of matched
pairs of the two input sequences. The second algorithm uses a balanced binary
search tree for DS and its time and space complexities are O(Rlog L+n) and
O(R), where L is the length of the longest common subsequence of X and Y. The
third algorithm uses an ordered vector for DS and its time and space
complexities are O(nL) and O(R). | | Source: | arXiv, 1508.5553 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER