A Simple Algorithm for Finding Exact Common Repeats

Inbok LEE  Yoan PINZON  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E90-D   No.12   pp.2096-2099
Publication Date: 2007/12/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e90-d.12.2096
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm Theory
Keyword: 
combinatorics,  suffix arrays,  DNA repeats,  

Full Text: PDF>>
Buy this Article




Summary: 
Given a set of strings U = {T1, T2, ...,T}, the longest common repeat problem is to find the longest common substring that appears at least twice in each string, considering direct, inverted, and mirror repeats. We define the generalised longest common repeat problem and present a linear time solution.