A substring-substring LCS data structure
A substring-substring LCS data structure
复制标题
子串-子串 LCS 数据结构
DOI：
10.1016/j.tcs.2018.06.034
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Y. Sakai
中科院分区：
文献类型：
--
作者：
Y. Sakai
对于任意具有可能具有对角边的网格单元的矩形网格图，我们提出了一种数据结构，该结构可以在时间上线性地构造图中的网格单元数目，并且支持对图中任意一对顶点之间的最短路径的线性时间查询。适当地设置具有对角线边的网格单元的位置，可以用这种数据结构在线性时间内求解最长公共子序列问题的局部变体或某些相关问题。
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.
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Shuhei Denzumi
通讯作者：
Shuhei Denzumi
在 STDk/3[k ;
DOI：
--
发表时间：
2008
期刊：
Discrete Mathematics 308
影响因子：
--
作者：
Y. Hiramine;C. Suetake;K. Akiyama C. Suetake
通讯作者：
K. Akiyama C. Suetake