LCS & edit distance

Overview

Comparing two strings is the classic 2-D dynamic program. Build a table indexed by prefix lengths: dp[i][j] is the answer for the first i characters of one string and the first j of the other. Longest common subsequence grows the diagonal by one whenever the characters match and otherwise takes the better neighbour; edit distance (Levenshtein) counts the cheapest sequence of insertions, deletions and substitutions. The two share a table shape and differ only in the recurrence — LCS maximises a match, edit distance minimises a cost.

Why it matters

Every git diff, every spell-checker suggestion, every DNA sequence alignment and every fuzzy-search ranking is this algorithm. Edit distance is how a search box decides that "recieve" meant "receive", and LCS is how a diff decides which lines are unchanged. Knowing the table shape means you can adapt it — weighted edits, restricted operations, alignment output — rather than reaching for a library and hoping.

Core concepts

Prefix indexing. dp[i][j] covers a[0..i-1] and b[0..j-1]. Row and column 0 represent an empty prefix, which is why the table has (la+1) x (lb+1) entries — the off-by-one that trips most first attempts.

LCS recurrence. If a[i-1] == b[j-1], the characters pair up: dp[i][j] = dp[i-1][j-1] + 1. Otherwise drop one character from either string and keep the better: max(dp[i-1][j], dp[i][j-1]).

Edit-distance recurrence. Base cases are real work here: dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything). Then a match costs nothing (dp[i-1][j-1]), and a mismatch is 1 + min(substitute, delete, insert).

Subsequence, not substring. LCS allows gaps — "ace" is a subsequence of "abcde". Contiguity is a different problem (see the matrix-DP lesson).

Flattened 2-D arrays. In C a (la+1) x (lb+1) table is usually one allocation indexed dp[i*W + j] with W = lb+1. Getting W wrong is the single most common source of garbage results.

Space. Each row depends only on the previous one, so two rows suffice for the score — but the full table is required to reconstruct the actual alignment.

Syntax notes

#include <stdlib.h>
#include <string.h>

int lcs(const char *a, const char *b) {
    int la = (int)strlen(a), lb = (int)strlen(b), W = lb + 1;   /* row stride */
    int *dp = calloc((size_t)(la + 1) * W, sizeof *dp);         /* row/col 0 = empty prefix */
    if (!dp) return -1;
    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++)
            dp[i*W + j] = (a[i-1] == b[j-1])
                ? dp[(i-1)*W + (j-1)] + 1
                : (dp[(i-1)*W + j] > dp[i*W + (j-1)]
                     ? dp[(i-1)*W + j] : dp[i*W + (j-1)]);
    int r = dp[la*W + lb];
    free(dp);
    return r;
}

Key points:

• W = lb + 1 is the stride; every index is i*W + j.
• Indices into the strings are i-1 / j-1 because row 0 is the empty prefix.
• calloc gives the zero base row/column that LCS needs for free; edit distance must fill them explicitly.

Lesson

Comparing two strings gives two staples: the longest common subsequence (characters in order, gaps allowed) and the edit distance (min inserts/deletes/substitutions). Both fill a 2-D table where each cell depends on its up, left, and diagonal neighbours.

Code examples

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
static int lcs(const char*a,const char*b){int la=strlen(a),lb=strlen(b),W=lb+1;int*dp=calloc((la+1)*W,sizeof(int));for(int i=1;i<=la;i++)for(int j=1;j<=lb;j++)dp[i*W+j]=(a[i-1]==b[j-1])?dp[(i-1)*W+j-1]+1:(dp[(i-1)*W+j]>dp[i*W+j-1]?dp[(i-1)*W+j]:dp[i*W+j-1]);int r=dp[la*W+lb];free(dp);return r;}
static int edit(const char*a,const char*b){int la=strlen(a),lb=strlen(b),W=lb+1;int*dp=malloc((la+1)*W*sizeof(int));for(int i=0;i<=la;i++)dp[i*W]=i;for(int j=0;j<=lb;j++)dp[j]=j;for(int i=1;i<=la;i++)for(int j=1;j<=lb;j++){if(a[i-1]==b[j-1])dp[i*W+j]=dp[(i-1)*W+j-1];else{int m=dp[(i-1)*W+j];if(dp[i*W+j-1]<m)m=dp[i*W+j-1];if(dp[(i-1)*W+j-1]<m)m=dp[(i-1)*W+j-1];dp[i*W+j]=m+1;}}int r=dp[la*W+lb];free(dp);return r;}
int main(void){
    printf("LCS(\"ABCBDAB\",\"BDCAB\") = %d\n", lcs("ABCBDAB","BDCAB"));
    printf("edit distance(\"kitten\",\"sitting\") = %d\n", edit("kitten","sitting"));
    return 0;
}

Line by line

Common mistakes

Confusing subsequence with substring; forgetting edit distance's base row/column.

Debugging tips

Compiler errors and warnings:

• warning: comparison of integer expressions of different signedness — strlen returns size_t; cast to int once up front.
• -Wmaybe-uninitialized if you used malloc for LCS and never wrote row 0.

Runtime symptoms:

• Answers are wildly wrong or the program crashes. The stride is wrong — it must be lb + 1, not lb. This is the dominant bug.
• Off-by-one in the result. You indexed the strings with a[i] instead of a[i-1].
• Edit distance returns 0 for unrelated strings. You used calloc and never filled dp[i][0] = i / dp[0][j] = j; unlike LCS, edit distance needs real base cases.
• LCS returns a substring length. You reset to 0 on mismatch — that is longest common substring, a different problem.

Technique: print the whole table for two short strings (say 4x4). The diagonal structure of an LCS table is instantly recognisable, and a wrong stride shows up as visible garbage.

Memory safety

• Size overflow. (la + 1) * (lb + 1) can overflow int for long inputs — compute in size_t as shown, and bound the input lengths before allocating.
• Check the allocation. A large table is exactly where calloc fails; handle NULL rather than dereferencing it.
• Initialisation differs by problem. LCS is fine with calloc's zeros; edit distance must write its base row and column or it reads meaningless zeros.
• Bounds. Every access is dp[i*W + j] with 0 <= i <= la, 0 <= j <= lb. A mismatched stride does not fault — it silently reads the wrong cell, which is why the bug is so hard to spot.
• Free once, on every path, and never return a value read from the table after freeing it.

Real-world uses

Concrete uses: git diff and diff compute a longest common subsequence over lines. Spell checkers and search engines rank suggestions by edit distance. Bioinformatics aligns DNA and protein sequences with weighted variants (Needleman-Wunsch is edit distance with a scoring matrix). Plagiarism detection, record linkage and fuzzy joins all use these scores.

Professional best practices:

Beginner:

• Write the stride into a named variable and use it everywhere.
• Draw the table for a tiny example before coding.

Intermediate:

• Use the two-row rolling form when you only need the score; keep the full table when you must output the alignment.
• For very long inputs consider Hirschberg's algorithm (linear space, still produces the alignment).
• Be explicit about which operations are allowed and what they cost — "edit distance" means different things in different products.

Practice tasks

1. (Beginner) LCS length. Implement int lcs(const char *a, const char *b). Example: "ABCBDAB", "BDCABA" -> 4. Concepts: prefix table, stride.

2. (Beginner) Edit distance. Implement int edit(const char *a, const char *b) with the explicit base row/column. Example: "kitten", "sitting" -> 3. Concepts: min of three operations.

3. (Intermediate) Rolling rows. Rewrite LCS to use only two rows and confirm it matches the full-table version. Concepts: space reduction, dependency analysis.

4. (Intermediate) Reconstruct the subsequence. Extend LCS to output the actual common subsequence string. Hint: walk backwards from dp[la][lb], moving diagonally on a match. Concepts: DP reconstruction.

Summary

String comparison uses a 2-D table indexed by prefix lengths, with row and column 0 standing for the empty prefix — hence a (la+1) x (lb+1) table and a[i-1] when reading characters. LCS extends the diagonal on a match and otherwise takes the better neighbour; edit distance fills a real base row and column, then takes 1 + min(substitute, delete, insert) on a mismatch. In C the table is normally one flat allocation indexed i*W + j with W = lb + 1, and a wrong stride is the classic silent bug. Two rolling rows give the score; keep the full table when you need the alignment itself.

Practice with these exercises

• Longest common subsequence
• Edit distance