Longest Common Subsequence in C and C++: Dynamic Programming, Linear Memory and a Working Diff

Written as plain recursion, the longest common subsequence of two 14-letter strings with no letter in common takes 80,233,199 function calls. The dynamic-programming table for the same two strings has 225 cells. That gap is the whole reason the longest common subsequence (LCS) problem is the standard first example of dynamic programming, and the same table, built over lines instead of letters, is how a diff tool decides which lines changed.

This guide explains the LCS recurrence, fills and reads back the table step by step, computes the length in linear memory, and builds a working line diff on top of it, in C and C++. It also measures the cost of the naive recursion, the time and memory of the table version up to 8,000 letters, and four mistakes the tests catch. Every program was compiled and run for this article on Ubuntu 24.04 (x86-64), and again under WSL and with MSVC 19.44 on Windows: C with GCC 13.3 and Clang 18.1.3 under -std=c11 and -std=c17, C++ with g++ 13.3 and clang++ 18.1.3 under -std=c++17 and -std=c++20, all with -Wall -Wextra -pedantic -Werror and no warnings. The tests run clean under AddressSanitizer, UndefinedBehaviorSanitizer and Valgrind, the diff agrees with GNU diff --minimal on 300 random file pairs, and every output block is captured verbatim. The code is in two GitHub repositories whose workflows repeat these checks on each commit.

What Is the Longest Common Subsequence?

The longest common subsequence (LCS) of two sequences is the longest sequence that appears in both in the same order, though not necessarily in consecutive positions. For ABCBDAB and BDCABA, one LCS is BCBA, of length 4. It is solved by dynamic programming in O(n·m) time, and it underlies diff tools, version control and DNA comparison.

A subsequence keeps elements in order but may skip some; a substring may not skip any. The difference changes both the answers and the algorithm:

An LCS is often not unique. BCBA, BCAB and BDAB are all common subsequences of length 4 for the pair above, and which one a program returns depends only on how it breaks ties.

The LCS Recurrence

Let L(i, j) be the length of the LCS of the first i letters of a and the first j letters of b. Compare the last letters of those two prefixes:

• If they match, that letter can end a longest common subsequence, so L(i, j) = L(i − 1, j − 1) + 1.
• If they differ, at least one of the two letters is not in the LCS, so drop one or the other and keep the better result: L(i, j) = max(L(i − 1, j), L(i, j − 1)).
• If either prefix is empty, L(i, j) = 0.

The answer is L(n, m). Written directly as a recursive function, the recurrence is correct but slow, because the two calls in the “differ” case reach the same smaller subproblems by many different routes. naive_recursion.c counts the calls for random DNA strings and for strings with no letter in common, the worst case:

 length   calls, random DNA   calls, no common letter   table cells
      2                  11                        11             9
      4                  26                       139            25
      6                 261                      1847            49
      8                 362                     25739            81
     10               15341                    369511           121
     12              117850                   5408311           169
     14              141953                  80233199           225

In the worst case every pair of letters differs, so every call branches twice. The number of calls is then 2·C(2n, n) − 1, where C is the binomial coefficient: for n = 14, 2 × 40,116,600 − 1 = 80,233,199, exactly the count measured. Every two extra letters multiply the work by about 15. The table never fills more than (n + 1)² cells, 225 here, because there are only that many different subproblems. Storing each answer once, instead of recomputing it, is what dynamic programming means; the Fibonacci series and the knapsack problem are the other two standard examples.

Filling the LCS Table

The table has a row for each prefix of a and a column for each prefix of b, including the empty ones. Row 0 and column 0 are zero, and every other cell depends only on the cells above, to the left and diagonally up-left, so filling the rows from top to bottom works:

The C version stores the table as one flat array of 32-bit cells and checks that its size cannot overflow before allocating it:

/* Table cells are 32-bit: an LCS is never longer than the shorter input. */
typedef uint32_t cell;

/* Allocates the (n+1) x (m+1) table, or returns NULL if its size in bytes
 * would overflow size_t or the lengths do not fit a cell. */
static cell *alloc_table(size_t n, size_t m)
{
    if (n >= UINT32_MAX || m >= UINT32_MAX)
        return NULL;
    size_t rows = n + 1, cols = m + 1;
    if (cols > SIZE_MAX / rows || rows * cols > SIZE_MAX / sizeof(cell))
        return NULL;
    return malloc(rows * cols * sizeof(cell));
}

32-bit cells halve the memory of size_t cells on a 64-bit machine and are enough, because an LCS is never longer than the shorter input. The two checks matter for large inputs: (n + 1) * (m + 1) * 4 computed without them can wrap around to a small number, and the program would then write far past the end of the block it was given.

Reading the LCS Back From the Table

The table holds lengths, not letters. To recover one LCS, start at the bottom-right cell and walk back: at a matching pair of letters, that letter belongs to the LCS and the walk moves diagonally; otherwise it moves to whichever neighbour, above or to the left, holds the larger value. The green cells in Figure 1 are that walk.

char *lcs_string(const char *a, const char *b)
{
    size_t n = strlen(a), m = strlen(b);
    cell *L = alloc_table(n, m);
    if (L == NULL)
        return NULL;
#define AT(i, j) L[(i) * (m + 1) + (j)]          /* L[i][j] in the flat array */

    for (size_t i = 0; i <= n; ++i)
        for (size_t j = 0; j <= m; ++j) {
            if (i == 0 || j == 0)
                AT(i, j) = 0;
            else if (a[i - 1] == b[j - 1])
                AT(i, j) = AT(i - 1, j - 1) + 1;
            else
                AT(i, j) = AT(i - 1, j) >= AT(i, j - 1) ? AT(i - 1, j) : AT(i, j - 1);
        }

    size_t len = AT(n, m);
    char *out = malloc(len + 1);       /* allocated even when len is 0 */
    if (out != NULL) {
        out[len] = '\0';
        /* Walk back from L[n][m]: a match belongs to the LCS; otherwise
         * move towards the larger neighbour, up on a tie. */
        size_t i = n, j = m, k = len;
        while (i > 0 && j > 0) {
            if (a[i - 1] == b[j - 1]) {
                out[--k] = a[i - 1];
                --i;
                --j;
            } else if (AT(i - 1, j) >= AT(i, j - 1)) {
                --i;
            } else {
                --j;
            }
        }
    }
#undef AT
    free(L);
    return out;
}

When the cells above and to the left are equal, both directions lead to a longest common subsequence, and this code goes up. Going left instead would return a different LCS of the same length, which the tests accept: they check that the result is a common subsequence of the right length, not that it equals one particular string. The result is always allocated with malloc, even when it is empty, so a caller can free every result the same way.

Computing the LCS Length in Linear Memory

When only the length is needed, as in a similarity score, two rows of the table are enough, because each row depends only on the one before it:

size_t lcs_length(const char *a, const char *b)
{
    size_t n = strlen(a), m = strlen(b);
    if (m > n) {                         /* keep the rows as short as possible */
        const char *s = a; a = b; b = s;
        size_t t = n; n = m; m = t;
    }
    /* Two rows of the table are enough: row i needs only row i - 1. */
    size_t *prev = calloc(m + 1, sizeof *prev), *cur = calloc(m + 1, sizeof *cur);
    if (prev == NULL || cur == NULL) {
        free(prev);
        free(cur);
        return SIZE_MAX;
    }
    for (size_t i = 1; i <= n; ++i) {
        for (size_t j = 1; j <= m; ++j) {
            if (a[i - 1] == b[j - 1])
                cur[j] = prev[j - 1] + 1;
            else
                cur[j] = prev[j] > cur[j - 1] ? prev[j] : cur[j - 1];
        }
        size_t *t = prev; prev = cur; cur = t;
    }
    size_t result = prev[m];
    free(prev);
    free(cur);
    return result;
}

This uses memory proportional to the shorter string instead of the product of both lengths: about 128 KB for two 8,000-letter strings against 256 MB for the full table. Recovering the subsequence itself in linear memory is also possible, with a divide-and-conquer method published by Dan Hirschberg in 1975, “A Linear Space Algorithm for Computing Maximal Common Subsequences”, which runs the two-row pass forwards and backwards to find where the LCS crosses the middle row, then recurses on the two halves.

A Complete LCS Example in C

/* lcs_demo.c - the longest common subsequence of a few string pairs, with
 * the table for the first pair.
 * Build: gcc -std=c11 -Wall -Wextra -pedantic lcs_demo.c lcs.c -o lcs_demo */
#include <stdio.h>
#include <stdlib.h>

#include "lcs.h"

static void show(const char *a, const char *b)
{
    char *common = lcs_string(a, b);
    if (common == NULL) {
        fputs("out of memory\n", stderr);
        exit(EXIT_FAILURE);
    }
    printf("%-14s %-14s length %zu: \"%s\"\n", a, b, lcs_length(a, b), common);
    free(common);                       /* always allocated, even when empty */
}

int main(void)
{
    puts("Table of LCS lengths for ABCBDAB and BDCABA:");
    lcs_print_table("ABCBDAB", "BDCABA", stdout);
    puts("");
    show("ABCBDAB", "BDCABA");
    show("BDCABA", "ABCBDAB");
    show("AGGTAB", "GXTXAYB");
    show("dynamic", "programming");
    show("abc", "xyz");
    show("", "anything");
    return 0;
}

Output:

Table of LCS lengths for ABCBDAB and BDCABA:
       B D C A B A
     0 0 0 0 0 0 0
  A  0 0 0 0 1 1 1
  B  0 1 1 1 1 2 2
  C  0 1 1 2 2 2 2
  B  0 1 1 2 2 3 3
  D  0 1 2 2 2 3 3
  A  0 1 2 2 3 3 4
  B  0 1 2 2 3 4 4

ABCBDAB        BDCABA         length 4: "BCBA"
BDCABA         ABCBDAB        length 4: "BDAB"
AGGTAB         GXTXAYB        length 4: "GTAB"
dynamic        programming    length 3: "ami"
abc            xyz            length 0: ""
               anything       length 0: ""

Swapping the two inputs changes the answer from BCBA to BDAB but not the length: both are longest common subsequences, and the walk-back meets its ties in a different order. The last two pairs show the empty cases, which return an allocated empty string rather than NULL.

Longest Common Subsequence in C++

The C++ version computes the table once in a template, so the same code finds the LCS of two strings, two std::vector<int>, or two lists of lines:

// The table of LCS lengths: cell (i, j) holds the LCS length of the first
// i elements of a and the first j elements of b. Works for std::string,
// std::string_view, std::vector and any other random-access sequence.
template <class A, class B>
std::vector<std::uint32_t> lcs_table(const A& a, const B& b)
{
    const std::size_t n = a.size(), m = b.size();
    if (n >= UINT32_MAX || m >= UINT32_MAX || (m + 1) > SIZE_MAX / (n + 1))
        throw std::length_error("inputs too long for an LCS table");
    std::vector<std::uint32_t> L((n + 1) * (m + 1), 0);
    auto at = [&](std::size_t i, std::size_t j) -> std::uint32_t& { return L[i * (m + 1) + j]; };
    for (std::size_t i = 1; i <= n; ++i)
        for (std::size_t j = 1; j <= m; ++j)
            at(i, j) = a[i - 1] == b[j - 1] ? at(i - 1, j - 1) + 1
                                            : std::max(at(i - 1, j), at(i, j - 1));
    return L;
}

// The positions (i in a, j in b) of one LCS, in order.
template <class A, class B>
std::vector<std::pair<std::size_t, std::size_t>> lcs_pairs(const A& a, const B& b)
{
    const std::vector<std::uint32_t> L = lcs_table(a, b);
    const std::size_t m = b.size();
    auto at = [&](std::size_t i, std::size_t j) { return L[i * (m + 1) + j]; };
    std::vector<std::pair<std::size_t, std::size_t>> pairs(at(a.size(), m));
    std::size_t i = a.size(), j = m, k = pairs.size();
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            pairs[--k] = {i - 1, j - 1};
            --i;
            --j;
        } else if (at(i - 1, j) >= at(i, j - 1)) {
            --i;
        } else {
            --j;
        }
    }
    return pairs;
}

lcs_pairs returns the positions of the matched elements rather than the elements themselves, which is what a diff needs: it says which line of the old file corresponds to which line of the new one. The string version and the diff are thin layers on top:

// One LCS of two strings.
std::string lcs(std::string_view a, std::string_view b)
{
    std::string result;
    for (auto [i, j] : lcs_pairs(a, b)) {
        (void)j;
        result += a[i];
    }
    return result;
}

// A line diff: ' ' for a line in both, '-' only in a, '+' only in b.
struct DiffLine {
    char op;
    std::string text;
};

std::vector<DiffLine> diff(const std::vector<std::string>& a, const std::vector<std::string>& b)
{
    std::vector<DiffLine> out;
    std::size_t i = 0, j = 0;
    for (auto [ai, bj] : lcs_pairs(a, b)) {
        for (; i < ai; ++i)
            out.push_back({'-', a[i]});
        for (; j < bj; ++j)
            out.push_back({'+', b[j]});
        out.push_back({' ', a[i]});
        ++i;
        ++j;
    }
    for (; i < a.size(); ++i)
        out.push_back({'-', a[i]});
    for (; j < b.size(); ++j)
        out.push_back({'+', b[j]});
    return out;
}

The program’s main runs these on four string pairs, two lists of integers and two short code fragments:

ABCBDAB / BDCABA: length 4, "BCBA"
AGGTAB / GXTXAYB: length 4, "GTAB"
dynamic / programming: length 3, "ami"
abc / xyz: length 0, ""
common subsequence of two int lists: 1 4 5 9 2 6
diff:
- int total = 0;
+ long long total = 0;
  for (int x : v)
      total += x;
+ std::cout << total;
  return total;

From LCS to diff

A diff is an LCS over lines. The lines in the LCS are the ones both files share; every other line of the old file was deleted, and every other line of the new file was added. The number of changed lines is therefore n + m − 2 × LCS, the smallest number of single-line deletions and insertions that turns one file into the other. lcs_diff builds the same table with strcmp in place of a character comparison and walks back the same way. Run on two versions of a small C program:

$ ./lcs_diff tests/data/before.c tests/data/after.c
  #include <stdio.h>
+ #include <string.h>
  
  int main(void)
  {
      char name[20];
      printf("Name: ");
-     gets(name);
+     if (fgets(name, sizeof name, stdin) == NULL)
+         return 1;
+     name[strcspn(name, "\n")] = '\0';
      printf("Hello, %s\n", name);
      return 0;
  }

The two files have 10 and 13 lines with 9 in common, so the diff shows 10 + 13 − 2 × 9 = 5 changed lines. Like diff, the program exits with status 0 when the files match, 1 when they differ and 2 on an error.

GNU diff uses Eugene Myers’ O(ND) algorithm, which finds the same shortest edit script far faster when the files are similar; its source notes that without --minimal it uses a heuristic that can give a slightly longer script on large inputs. To check lcs_diff against an independent implementation, tests/compare_gnu_diff.py generates random pairs of files and compares the number of changed lines with diff --minimal:

random file pairs where lcs_diff and GNU diff --minimal change the same number of lines: 300 of 300

Four Mistakes That Break an LCS Program

tests/mutations.py puts seven plausible mistakes into copies of lcs.c, builds each with AddressSanitizer and UndefinedBehaviorSanitizer, and runs the tests. One more change, a different tie-break, is included as a control: it must pass, because it still returns a correct LCS. Sanitizer reports are summarized as the error type and the place in lcs.c:

mistake                                              result
a match extends the cell above, not the diagonal     caught: a="ABCBDAB" b="BDCABA": got "?BDAB" and length 4, wanted length 4
min instead of max of the two neighbours             caught: AddressSanitizer: heap-buffer-overflow in lcs_string (lcs.c:86)
characters compared one position off                 caught: a="ABC" b="DEF": got "?" and length 0, wanted length 0
the two rows are never swapped                       caught: a="ABC" b="ABC": got "ABC" and length 0, wanted length 3
no room for the terminating NUL                      caught: AddressSanitizer: heap-buffer-overflow in lcs_string (lcs.c:80)
a literal returned for an empty LCS                  caught: AddressSanitizer: SEGV
the diff swaps - and +                               caught: AddressSanitizer: global-buffer-overflow in lcs_diff (lcs.c:176)
walk-back prefers left instead of up on a tie        passes: still a correct LCS
mistakes the tests miss: 0

Four of these are worth knowing:

• Plain recursion, covered above: correct, but 80 million calls for 14 letters.
• Off-by-one indexing. Row i of the table describes the first i letters, so it compares a[i - 1], not a[i]. Comparing a[i] and b[j] reads one letter ahead, and the terminating NUL at the end; for ABC and DEF, which have nothing in common, it returned a one-character string of garbage.
• Forgetting the terminating NUL. malloc(len) instead of malloc(len + 1) gives a buffer one byte short. AddressSanitizer reported a heap-buffer-overflow at the line that writes out[len] = '\0'; without it, the program would usually appear to work.
• Returning a string literal for the empty case. A function that returns malloc‘d memory for most inputs and "" for an empty result looks harmless, until the caller frees every result. free_literal.c does exactly that:

$ ./pitfall_free_literal
hello / world -> "llo"
abc / xyz -> ""
free(): invalid pointer
Aborted

Under AddressSanitizer the same program stopped with AddressSanitizer: SEGV in the call to free() at free_literal.c:35. Neither GCC 13.3 nor Clang 18.1.3 warned with -Wall -Wextra, at -O0 or -O2. GCC’s static analyzer did: compiled with -fanalyzer, it reported free_literal.c:35:9: warning: 'free' of 'r' which points to memory not on the heap [CWE-590] [-Wanalyzer-free-of-non-heap]. The rule that avoids it is simple: a function that returns allocated memory should return allocated memory every time, which is why lcs_string allocates even an empty result. (Sanitizer and analyzer reports here are summarized to the error, function and line.)

How Fast Is the LCS Table, and How Big?

How This Was Measured

All figures come from one machine, single-threaded, with no CPU pinning or frequency-scaling control and no percentiles.

    n   LCS   lcs_length ms  rows MB   lcs_string ms  table MB   ns per cell
 1000   637             0.8     0.02             1.3       4.0          0.83
 2000  1293             3.4     0.03             5.2      16.0          0.84
 4000  2599            26.2     0.06            38.6      64.0          1.64
 8000  5229           168.3     0.13           312.8     256.1          2.63

lcs_length only, best of 3:
    n  two rows KB  ns per cell
 1000           16         0.81
 2000           31         0.82
 3000           47         0.93
 4000           63         1.61
 5000           78         2.05
 6000           94         2.33
 7000          109         2.47
 8000          125         2.58
 9000          141         2.68
10000          156         2.77
11000          172         2.83
12000          188         2.88

Both functions do the same n² cell updates, so time grows with the square of the length: doubling from 4,000 to 8,000 letters took 6.4 times as long for lcs_length and 8.1 times for lcs_string, more than the factor of 4 the cell count alone predicts, because the cost per cell also rose. lcs_string took 1.5 to 1.9 times as long as lcs_length, but the real difference is memory: 256 MB of table against 0.13 MB of rows at 8,000 letters. At 46,000 letters the table would need about 8.5 GB.

The sweep shows the cost per cell of lcs_length stepping up from 0.8–0.9 ns to 1.6 ns between 3,000 and 4,000 letters, and climbing towards 2.9 ns after that. The step coincides with its two rows, 16 bytes per column, growing past the 48 KB L1 data cache of this CPU; that is an inference from where the step falls, not a profile. Storing the rows as 32-bit cells, as the full table already does, would halve their size and move the step to about twice the length.

One more number comes free with the random strings. For two random strings over four letters, the expected LCS length is a fixed fraction of their length, the Chvátal–Sankoff constant for an alphabet of 4. High-precision simulations by Ralf Bundschuh put it at 0.654361; the 8,000-letter pair above has an LCS of 5,229, or 0.654.

Key Takeaways

• The LCS is the longest sequence found in both inputs in order, not necessarily consecutive, and it is often not unique.
• The recurrence is 1 + diagonal on a match, otherwise the larger of above and left; plain recursion on it took 80,233,199 calls for 14 letters, where the table needs 225 cells.
• Walking back from the bottom-right cell recovers one LCS; the direction taken on ties decides which one.
• The length alone needs only two rows, 0.13 MB instead of 256 MB for 8,000 letters.
• A diff is an LCS over lines: n + m − 2 × LCS changed lines, which matched GNU diff --minimal on 300 of 300 random file pairs.
• Return allocated memory every time. A string literal returned for the empty case crashed the caller’s free(), and neither compiler warned with -Wall -Wextra.

Frequently Asked Questions

Conclusion

The longest common subsequence is a small problem with a long reach. The same table that teaches what dynamic programming is also drives every diff you have read in a code review, and the gap between 80 million recursive calls and 225 table cells is about the clearest argument for storing subproblem answers that any example offers.

The details that make an implementation trustworthy are the unglamorous ones: index arithmetic that stays one row behind the table, a table size checked before it is allocated, and a result that is allocated the same way every time. Comparing the output with brute force and with GNU diff is what shows those details are right. More dynamic programming and other algorithms built the same way are in the algorithms section.

Source Code and Tests

All programs on this page are in the dynamic-programming/lcs directory of the MYCPLUS C and C++ examples repositories:

Language	Repository directory	Build
C	mycplus/c-examples › dynamic-programming/lcs
C++	mycplus/cpp-examples › dynamic-programming/lcs

Build and test either one:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

What the build checks. The C version compiles with GCC and Clang under C11 and C17 and with MSVC /W4 /WX; the C++ version with g++ and clang++ under C++17 and C++20 and with MSVC /W4 /WX /permissive-; warnings are errors. Both check 10,000 random pairs of short strings against a brute-force search and 500 random diffs that must rebuild both inputs, and both print exactly the outputs on this page. On Linux, the workflows run everything under AddressSanitizer and UndefinedBehaviorSanitizer, and the C workflow also checks that free_literal crashes, that lcs_diff agrees with GNU diff --minimal on 300 random file pairs, and that each mutation is caught. They do not run the benchmark, whose figures came from one machine.

What I Verified

Each example directory contains run_all.sh for Ubuntu and WSL and run_all.ps1 for Windows, which run every check below and print one line per row.

Not covered: 32-bit builds, compilers newer than GCC 13.3 and Clang 18.1.3, Clang’s sanitizers on the test machine (they run in CI), timing on any other machine, and multibyte text: both versions compare bytes, so a UTF-8 letter of several bytes is compared byte by byte.