File Segmentations.h

↰ Parent directory (ADS/string)

The number of ways of writing a sequence X of n items as a concatenation of words, the counting version of the word break problem [see File WordBreak.h, which finds one of them].

Definition (ADS/string/Segmentations.h)

Detailed Description

  • countSegmentations(): D[ i ], the segmentations of X[ i .. n ), is the sum of D[ i + |w| ] over the words w of the list that occur in X at i, D[ n ] = 1, filled from the right in :math:` O( n sum_w |w| ) ` time and O( n ) space. With the automaton of Aho and Corasick on the words, the occurrences ending at each place come in one scan, and the time drops to :math:` O( n + sum_w |w| + occ ) ` for occ occurrences.

  • countDecodings(): the readings of a string of digits as letters, A = 1, …, Z = 26, the segmentations into the words 1, …, 26: D[ i ] = 0 if d_i = 0, else D[ i + 1 ] plus D[ i + 2 ] if d_i d_{i+1} is in 10 .. 26; :math:` Theta( n ) ` time and O( 1 ) space, the two last entries of D. On n digits 1 the count is the Fibonacci number :math:` F_{n+1} `.

The counts grow exponentially with n, and they are given modulo :math:` 2^{64} `. countSegmentations() takes any sequence S with size(), operator[] and the comparison of its items; the overload on std::string also takes string literals.

The contracts [see File Contract.h]: no word is empty, and the digits are in 0 .. 9. The functions are defined in Segmentations.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

    1. Aho, M. J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM 18(6), 333-340, 1975

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions