TY - JOUR

T1 - A substring–substring LCS data structure

AU - Sakai, Yoshifumi

N1 - Publisher Copyright:
© 2018 Elsevier B.V.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Algorithms

KW - Longest common subsequence

KW - Semi-local string comparison

KW - Shortest path

UR - http://www.scopus.com/inward/record.url?scp=85049618224&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049618224&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2018.06.034

DO - 10.1016/j.tcs.2018.06.034

M3 - Article

AN - SCOPUS:85049618224

SN - 0304-3975

VL - 753

SP - 16

EP - 34

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -