File SuffixApplications.h

↰ Parent directory (ADS/string)

Problems on strings solved by a suffix array [see File SuffixArray.h] or a suffix tree [see File SuffixTree.h], beyond the book (section 10.4 of the notes and their classical companions).

Definition (ADS/string/SuffixApplications.h)

Detailed Description

A substring that occurs twice is a common prefix of two suffixes, and the suffixes that share a prefix of length L are a range of SA whose LCP entries are all at least L: hence a scan of LCP, or a visit of the internal nodes of the suffix tree, answers the questions on the repeats in O( n ) time.

  • longestRepeatedSubstring(): the largest entry of LCP, O( n ), against the :math:` O( n^2 ) ` of the dynamic programming of a string against itself;

  • repeatedSubstring( SA , L , C ), the query of text mining of section 10.4.3: a substring of length L that occurs at least C times is a run of at least C - 1 entries of LCP that are at least L, one scan, O( n ), against the :math:` O( n^2 L ) ` of counting every substring;

  • distinctSubstrings(): each suffix SA[ r ] adds the n - SA[ r ] prefixes less the LCP[ r - 1 ] it shares with the previous one, hence :math:` n ( n + 1 ) / 2 - sum_r LCP[ r ] `, O( n );

  • longestCommonSubstring( S , k ): the longest substring common to at least k of the m strings of S, on the suffix array of their join with m distinct separators (an integer alphabet): a window of ranks that covers suffixes of k distinct strings, slid by two pointers, whose common prefix is the lce() of its two ends, :math:` O( N ) ` for N the total length, against the :math:` O( |P| |T| ) ` of the dynamic programming for two strings [see File LongestCommonSubsequence.h] and the generalized suffix tree with the colors of Hui for any k;

  • maximalRepeats(): the maximal repeats, the substrings that occur twice and cannot be extended to the right (an internal node, Property 10.8) nor to the left (the symbols before their occurrences are not all the same, or one occurrence starts the text): the internal nodes whose leaves are left-diverse, by one visit from the leaves up, O( n ), as in Gusfield;

  • proximity( SA , P , Q , k ), the proximity search of section 10.4.3: the occurrences of P and of Q, sorted together, have an occurrence of each at distance at most k exactly when two adjacent ones of different patterns do, :math:` O( |P| + |Q| + occ log occ ) `;

  • kMismatches( T , P , k ), Algorithm 10.4 (section 10.4.1): the places where P occurs with at most k substitutions, each checked by at most k

    • 1 longest common extensions of a suffix of T and a suffix of P, both suffixes of T::P, by the range minima of its LCP in O( 1 ): :math:` O( n k

    ) ` after O( n + p ) preprocessing, against the O( n p ) of trying every place, as in Landau and Vishkin;

  • lz77ByTree( T ), the parsing of Ziv and Lempel by the suffix tree of section 10.4.2: the phrase at i copies the longest prefix of the suffix i that starts earlier, found by walking down along the suffix i while the least leaf below the next node is smaller than i, the least leaves computed by one visit; the copy is taken from the farthest occurrence, the least leaf, :math:` O( n log sigma ) ` in all (Theorem 10.13, which states O( n ) with perfect hashing at the nodes). The phrase is the triple ( distance , length , next symbol ), the last one without the symbol when the copy reaches the end of T; decodeCopyPhrases() inverts it.

The contracts [see File Contract.h]: k is at least 1 and at most the number of strings for longestCommonSubstring(), C at least 1; the parsing decodes to the text (an audit). The functions are defined in SuffixApplications.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 10

  1. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, doi:10.1017/CBO9780511574931, sections 7.4-7.12

      1. Hui, Color set size problem with applications to string matching, Proceedings of the 3rd Symposium on Combinatorial Pattern Matching (CPM), LNCS 644, 230-243, 1992, doi:10.1007/3-540-56024-6_19

    1. Abouelhoda, S. Kurtz, E. Ohlebusch, Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms 2(1), 53-86, 2004, doi:10.1016/S1570-8667(03)00065-0

    1. Landau, U. Vishkin, Efficient string matching with k mismatches, Theoretical Computer Science 43, 239-249, 1986, doi:10.1016/0304-3975(86)90178-7

  1. Ziv, A. Lempel, A universal algorithm for sequential data compression, IEEE Transactions on Information Theory 23(3), 337-343, 1977, doi:10.1109/TIT.1977.1055714

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions