File StringMatching.h

↰ Parent directory (ADS/string)

The exact string matching, beyond the book: the occurrences of a pattern P of m characters in a text T of n characters, the places :math:` s in [ 0 , n - m ] ` with :math:` T[ s .. s + m - 1 ] = P `.

Definition (ADS/string/StringMatching.h)

Detailed Description

These are the algorithms of the textbooks, which count their comparisons of characters where asked; the engineered search of Namespace ADS is StringSearcher [see File StringSearch.h].

  • naiveMatching() tries each shift of P along T, :math:` O( n m ) `;

  • kmp(), the algorithm of Knuth, Morris and Pratt, first computes the failure function of P, :math:` F[ q ] ` the length of the longest proper border of :math:` P[ 0 .. q - 1 ] ` (a border is both a prefix and a suffix), and then scans T once, shifting P by its failure on a mismatch, so that no character of T is compared again after a match: at most :math:` 2 n ` comparisons, :math:` Theta( n + m ) ` time. strongFailure() is the failure function improved by Knuth, :math:` G[ q ] = G[ F[ q ] ] ` if :math:` P[ F[ q ] ] = P[ q ] ` and :math:` F[ q ] ` otherwise: a mismatch on P[ q ] would repeat on the character after the border; kmpStrong() is kmp() with it, which never compares a character of T twice against the same character of P;

  • boyerMoore() compares P from right to left and shifts by the larger of the bad character rule (the last place of the character of T in P) and the strong good suffix rule (the next place of the suffix matched, preceded by another character, or the longest prefix of P that is its suffix), both prepared in :math:` O( m + sigma ) ; :math: O( n / m ) ` comparisons at best, :math:` O( n m ) ` in the worst case for all the occurrences (O( n ) for the first one);

  • horspool() shifts by the bad character of the last character of the window alone, :math:` mathit{shift}[ c ] = m - 1 - max{ i < m - 1 : P[ i ] = c } ` (m if none), the simplest and often the fastest of the family on large alphabets, :math:` O( n m ) ` in the worst case;

  • shiftOr() (m <= 64) keeps in a word D the prefixes of P that end at the current character, a clear bit i when :math:` P[ 0 .. i ] ` does, :math:` D leftarrow ( D ll 1 ) vee B[ T[ j ] ] ` with the bit i of :math:` B[ c ] ` clear if :math:` P[ i ] = c , :math: Theta( n ) ` word operations;

  • zFunction() gives :math:` Z[ i ] = mathrm{lcp}( S , S[ i .. ] ) ` for every i in :math:` Theta( n ) , from the Z-box :math: [ l , r ) ` that reaches farthest: inside it :math:` Z[ i ] ge min( Z[ i - l ] , r - i ) , and only the characters past r are compared; zMatching() extends the boxes of T against P in the same way, :math: Theta( n + m ) `;

  • twoWay() is the Two-Way algorithm of Crochemore and Perrin [see File StringSearch.h]: the critical factorization P = u v by two maximal suffixes, v compared from left to right and u from right to left, at most :math:` 2 n ` comparisons in O( 1 ) extra space.

The empty pattern occurs at every place 0 , … , n.

The contracts [see File Contract.h]: the failure function gives proper borders, the Z-function values that fit the string, and every search the occurrences of naiveMatching() (checked at level 3). The operations are defined in StringMatching.tpp.

    1. Knuth, J. H. Morris, V. R. Pratt, Fast pattern matching in strings, SIAM Journal on Computing 6(2), 323-350, 1977, doi:10.1137/0206024

    1. Boyer, J. S. Moore, A fast string searching algorithm, Communications of the ACM 20(10), 762-772, 1977, doi:10.1145/359842.359859

    1. Horspool, Practical fast searching in strings, Software: Practice and Experience 10(6), 501-506, 1980, doi:10.1002/spe.4380100608

    1. Baeza-Yates, G. H. Gonnet, A new approach to text searching, Communications of the ACM 35(10), 74-82, 1992, doi:10.1145/135239.135243

  1. Gusfield, Algorithms on Strings, Trees and Sequences, Cambridge University Press, 1997, section 1.4, doi:10.1017/CBO9780511574931

  1. Crochemore, D. Perrin, Two-way string-matching, Journal of the ACM 38(3), 650-674, 1991, doi:10.1145/116825.116845

  1. Charras, T. Lecroq, Handbook of Exact String Matching Algorithms, King’s College Publications, 2004, ISBN 0-9543006-4-5

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/string/impl/StringMatching.tpp

  • cstddef

  • cstdint

  • string_view

  • vector

Included By

Namespaces

Functions