File StringBreaking.h

↰ Parent directory (ADS/string)

Breaking a string: a string of length L has to be cut at the places 0 < c_1 < … < c_n < L, and each cut costs the length of the piece it splits; the order of the cuts decides the total cost.

Definition (ADS/string/StringBreaking.h)

Detailed Description

With the sentinels w_0 = 0 and w_{n+1} = L, D[ i ][ j ], the least cost of the cuts strictly between w_i and w_j, is 0 if j = i + 1 and otherwise :math:` w_j - w_i + min_{i < k < j} ( D[ i ][ k ] + D[ k ][ j ] ) , the scheme of the chain of matrices and of the optimal search tree, which takes :math: Theta( n^3 ) ` time. The cost :math:` w_j - w_i ` satisfies the quadrangle inequality as an equality and is monotone on the intervals, so the largest optimal split K[ i ][ j ] lies between K[ i ][ j - 1 ] and K[ i + 1 ][ j ] (Knuth for the search trees, Yao in general): the candidates of all the intervals of one length add up to O( n ), and the table costs :math:` Theta( n^2 ) ` time and space. stringBreakingOrder() reads an optimal order back from the splits, each cut before those of its two pieces.

The cut places are any integer type; the overloads on std::int64_t also take a braced list.

The contracts [see File Contract.h]: the places are strictly increasing and inside ( 0 , L ); the order is a permutation of the places whose cost is the least one (an audit). The functions are defined in StringBreaking.tpp.

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

    1. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009, problem 15-9

    1. Knuth, Optimum binary search trees, Acta Informatica 1(1), 14-25, 1971

    1. Yao, Efficient dynamic programming using quadrangle inequalities, Proceedings of the 12th ACM Symposium on Theory of Computing, 429-435, 1980

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions