File LongestCommonSubsequence.h

↰ Parent directory (ADS/string)

The longest common subsequence (LCS) of P and T, the reality check of section 13.7: DP[ i ][ j ], its length for the prefixes P( i ) and T( j ), is 0 if i = 0 or j = 0, DP[ i - 1 ][ j - 1 ] + 1 if p_{i-1} = t_{j-1}, and :math:` max{ DP[ i - 1 ][ j ] , DP[ i ][ j - 1 ] } ` otherwise, Theta( m n ).

Definition (ADS/string/LongestCommonSubsequence.h)

Detailed Description

lcsMemo() is the memoized version of the book, which solves only the subproblems that it reaches. diff() reads the differences from the table in O( m + n ), as the Unix command does on the lines of two files (exercise 13.10): the items of P only marked ‘-’, the items of T only ‘+’, the common ones ‘ ‘. The longest common substring, contiguous, has DP[ i ][ j ] = DP[ i - 1 ][ j - 1 ] + 1 if p_{i-1} = t_{j-1} and 0 otherwise, its length the largest entry (exercise 13.2).

The contracts [see File Contract.h]: lcs() gives a subsequence of both strings as long as the table says (checked at level 3), and longestCommonSubstring() a substring of both. The operations are defined in LongestCommonSubsequence.tpp.

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

    1. Hunt, M. D. McIlroy, An algorithm for differential file comparison, Computing Science Technical Report 41, Bell Laboratories, 1976

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions