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 -