Name
Abstract | ||
|---|---|---|
Given a set of strings $\mathcal{U} = \{T_{1}, T_{2}, . . . , T_{\ell}\}$, the longest common repeat problem is to find the longest common substring that appears at least twice in each string of $\mathcal{U}$, considering direct, inverted, mirror as well as everted repeats. In this paper we define the generalised longest common repeat problem, where we can set the number of times that a repeat should appear in each string. We present a linear time algorithm for this problem using the suffix array. We also show an application of our algorithm for finding a longest common substring which appears only in a subset $\mathcal{U}^{\prime}$ of $\mathcal{U}$ but not in $\mathcal{U}$-$\mathcal{U}^{\prime}$. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11575832_21 | SPIRE |
Keywords | Field | DocType |
everted repeat,linear time algorithm,generalised longest common repeat,longest common repeat problem,suffix array,longest common substring,inverted repeat,inverted repeats | Prime (order theory),Discrete mathematics,Combinatorics,Algorithm,Suffix array,Time complexity,String (computer science),Mathematics,Longest common substring problem | Conference |
Volume | ISSN | ISBN |
3772 | 0302-9743 | 3-540-29740-5 |
Citations | PageRank | References |
3 | 0.46 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Inbok Lee | 1 | 58 | 10.49 |
| Yoan José Pinzón Ardila | 2 | 7 | 1.86 |