An Efficient Algorithm for a New Constrained LCS Problem
2016
The solution to a generalized longest common subsequence problem is addressed in this paper. In this problem, two given sequences of their length s and t must be included as the subsequences of the two main sequences A and B, and the result subsequences must be the longest. If the lengths of the two main sequences A and B are n and m, and the lengths of their two constrained sequences are s and t respectively, the time complexity of the dynamic programming algorithm presented in this paper to solve the new generalized LCS problem must be O(nmst).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
10
References
1
Citations
NaN
KQI