Longest Common Extensions via Fingerprinting

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

View graph of relations

The longest common extension (LCE) problem is to preprocess a string in order to allow for a large number of LCE queries, such that the queries are efficient. The LCE value, LCE s (i,j), is the length of the longest common prefix of the pair of suffixes starting at index i and j in the string s. The LCE problem can be solved in linear space with constant query time and a preprocessing of sorting complexity. There are two known approaches achieving these bounds, which use nearest common ancestors and range minimum queries, respectively. However, in practice a much simpler approach with linear query time, no extra space and no preprocessing achieves significantly better average case performance. We show a new algorithm, Fingerprint k , which for a parameter k, 1 ≤ k ≤ [log n], on a string of length n and alphabet size σ, gives O(k n1/k) query time using O(k n) space and O(k n + sort(n,σ)) preprocessing time, where sort(n,σ) is the time it takes to sort n numbers from σ. Though this solution is asymptotically strictly worse than the asymptotically best previously known algorithms, it outperforms them in practice in average case and is almost as fast as the simple linear time algorithm. On worst case input, this new algorithm is significantly faster in practice compared to the simple linear time algorithm. We also look at cache performance of the new algorithm, and we show that for k = 2, cache optimization can improve practical query time.
Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications : 6th International Conference, LATA 2012 A Coruña, Spain, March 5-9, 2012 Proceedings
PublisherSpringer
Publication date2012
Pages119-130
ISBN (print)978-3-642-28331-4
ISBN (electronic)978-3-642-28332-1
DOIs
StatePublished

Conference

ConferenceThe 6th International Conference on Language and Automata Theory and Applications, LATA
CountrySpain
CityCoruña
Period05/03/1209/03/12
NameLecture Notes in Computer Science
Volume7183
ISSN (Print)0302-9743
CitationsWeb of Science® Times Cited: No match on DOI
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 7742979