Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
| Autor: | Richard C. T. Lee, Yue-Li Wang, J. J. Liu |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Statistics and Probability
Numerical Analysis Control and Optimization Algebra and Number Theory Matching (graph theory) Applied Mathematics General Mathematics String (computer science) Longest increasing subsequence Substring Combinatorics Longest common subsequence problem Character (mathematics) Partial word Function composition Mathematics |
| Zdroj: | Journal of Complexity. 24:173-184 |
| ISSN: | 0885-064X |
| DOI: | 10.1016/j.jco.2007.06.003 |
| Popis: | In this paper, we propose an O(min{mN,Mn}) time algorithm for finding a longest common subsequence of strings X and Y with lengths M and N, respectively, and run-length-encoded lengths m and n, respectively. We propose a new recursive formula for finding a longest common subsequence of Y and X which is in the run-length-encoded format. That is, Y=y"1y"2...y"N and X=r"1^l^"^1r"2^l^"^2...r"m^l^"^m, where r"i is the repeated character of run i and l"i is the number of its repetitions. There are three cases in the proposed recursive formula in which two cases are for r"i matching y"j. The third case is for r"i mismatching y"j. We will look specifically at the prior two cases that r"i matches y"j. To determine which case will be used when r"i matches y"j, we have to find a specific value which can be obtained by using another of our proposed recursive formulas. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect