Longest common subsequence

Challenge

Implement:

int lcs(const char *a, const char *b);

Return the length of the Longest Common Subsequence (characters in order, not necessarily contiguous) of a and b.

Input format

Two strings.

Output format

LCS length.

Constraints

Use a 2-D table of size (|a|+1)x(|b|+1).

Starter code

#include <stddef.h>
/* Length of the Longest Common Subsequence of strings a and b. */
int lcs(const char *a,const char *b){ (void)a;(void)b; return 0; }

Common mistakes

Confusing subsequence (non-contiguous) with substring (contiguous).

Edge cases to handle

Empty string -> 0.

Background lessons

• LCS & edit distance