Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda

**Computing Longest Common Substring/Subsequence of Non-linear Texts**

Abstract: |

A non-linear text is a directed graph where each vertex is labeled with a string.
In this paper, we introduce the longest common substring/subsequence problems on
non-linear texts.
Firstly, we present an algorithm to compute the longest common substring
of non-linear texts G_{1} and G_{2} in O(|E_{1}||E_{2}|) time and
O(|V_{1}||V_{2}|) space, when at least one of G_{1} and G_{2} is acyclic.
Here, V_{i} and E_{i} are the sets of vertices and arcs of input non-linear text G_{i},
respectively, for 1 ≤ i ≤ 2.
Secondly, we present algorithms to compute the longest common
subsequence
of G_{1} and G_{2} in O(|E_{1}||E_{2}|) time and O(|V_{1}||V_{2}|) space,
when both G_{1} and G_{2} are acyclic,
and in O(|E_{1}||E_{2}| + |V_{1}||V_{2}| log |Σ|) time and O(|V_{1}||V_{2}|) space
if G_{1} and/or G_{2} are cyclic,
where, Σ denotes the alphabet. |

Download paper: | |||

PostScript | BibTeX reference |

Download presentation: |