Longest Common Extensions via Fingerprinting

Philip Bille, Inge Li Gørtz, Jesper Kristensen

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Abstract

    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
    Publication statusPublished - 2012
    EventThe 6th International Conference on Language and Automata Theory and Applications, LATA - Coruña, Spain
    Duration: 5 Mar 20129 Mar 2012

    Conference

    ConferenceThe 6th International Conference on Language and Automata Theory and Applications, LATA
    CountrySpain
    CityCoruña
    Period05/03/201209/03/2012
    SeriesLecture Notes in Computer Science
    Volume7183
    ISSN0302-9743

    Fingerprint Dive into the research topics of 'Longest Common Extensions via Fingerprinting'. Together they form a unique fingerprint.

    Cite this