A substring–substring LCS data structure

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


For any rectangular grid graph with grid units each potentially having a diagonal edge, we propose a data structure that is constructible in time linear in the number of grid units in the graph and supports linear-time queries of a shortest path between any pair of vertices in the graph. Setting the position of grid units having a diagonal edge appropriately, we can use this data structure to solve a local variant of the longest common subsequence problem or certain related problems in linear time.

Original languageEnglish
Pages (from-to)16-34
Number of pages19
JournalTheoretical Computer Science
Publication statusPublished - 2019 Jan 1


  • Algorithms
  • Longest common subsequence
  • Semi-local string comparison
  • Shortest path


Dive into the research topics of 'A substring–substring LCS data structure'. Together they form a unique fingerprint.

Cite this