Name
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(vertical bar E-1 parallel to E-2 vertical bar) time and O(vertical bar V-1 parallel to V-2 vertical bar) 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(vertical bar E-1 parallel to E-2 vertical bar) time and O(vertical bar V-1 parallel to V-2 vertical bar) space, when both G(1) and G(2) are acyclic, and in O(vertical bar E-1 parallel to E-2 vertical bar+vertical bar V-1 parallel to V-2 vertical bar log vertical bar Sigma vertical bar) time and O(vertical bar V-1 parallel to V-2 vertical bar) space if G(1) and/or G(2) are cyclic, where, Sigma denotes the alphabet. |
Year | Venue | Field |
|---|---|---|
2011 | PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2011 | Discrete mathematics,Substring index,Combinatorics,Substring,Longest common subsequence problem,Longest increasing subsequence,Longest palindromic substring,Computer science,Longest repeated substring problem,Subsequence,Longest common substring problem |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
3 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kouji Shimohira | 1 | 3 | 0.73 |
| Shunsuke Inenaga | 2 | 595 | 79.02 |
| Hideo Bannai | 3 | 620 | 79.87 |
| Masayuki Takeda | 4 | 902 | 79.24 |