Efficient algorithms for the longest common subsequence in \(k\)-length substrings

DOI10.1016/j.ipl.2014.05.009zbMath1371.68338arXiv1311.4552OpenAlexW2060273814MaRDI QIDQ2252645

Szymon Grabowski, Sebastian Deorowicz

Publication date: 18 July 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.4552

zbMATH Keywords

algorithmscombinatorial problemssparse dynamic programming\(\mathrm{LCS}k\)

Mathematics Subject Classification ID

Dynamic programming (90C39) Algorithms on strings (68W32)

Related Items (2)

Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings ⋮ A space efficient algorithm for the longest common subsequence in \(k\)-length substrings

Cites Work

• Unnamed Item
• Unnamed Item
• The longest common subsequence problem revisited
• Making data structures persistent
• A faster algorithm computing string edit distances
• Preserving order in a forest in less than logarithmic time and linear space
• Linear work suffix array construction
• A fast algorithm for computing longest common subsequences
• Sparse dynamic programming I
• Algorithms on Strings

This page was built for publication: Efficient algorithms for the longest common subsequence in \(k\)-length substrings