Longest common subsequence – Algorithms Practice

Print the length of the longest common subsequence of two words: the longest sequence of characters that appears, in order but not necessarily side by side, in both. For ABCB and BDCAB it is 3 (BCB).

What to build

A table that finds the length of the longest common subsequence of two words.

Requirements

Let L[i][j] be the answer for the first i characters of one word and the first j of the other.
Extend the diagonal cell when the last characters match, and otherwise take the larger neighbour.
Print L[n][m].

Input

Two lines, each with a word of 1 to 100 characters (no spaces). Upper and lower case are different characters.

Output

The length of the longest common subsequence.

Constraints

Each word has 1 to 100 characters, and upper and lower case are different.

Example

Input:

ABCB
BDCAB

Output:

Why it works

Either the last two characters match and can be used together, or at least one of them is not part of the answer and can be dropped.

Examples

Example 1 · Input

ABCB
BDCAB

Expected output

Example 2 · Input

abc
xyz

Expected output

Hints

Hint 1

L[i][j] = the LCS length of the first i characters of a and the first j of b; row 0 and column 0 are 0.

Hint 2

If a[i-1] == b[j-1], L[i][j] = L[i-1][j-1] + 1; otherwise the larger of L[i-1][j] and L[i][j-1].

Hint 3

Use strlen to get the two lengths.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>
#include <string.h>

int L[101][101];

int main(void) {
    char a[101], b[101];
    scanf("%100s %100s", a, b);
    int n = strlen(a), m = strlen(b);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) L[i][j] = L[i - 1][j - 1] + 1;
            else L[i][j] = L[i - 1][j] > L[i][j - 1] ? L[i - 1][j] : L[i][j - 1];
        }
    }
    printf("%d\n", L[n][m]);
    return 0;
}

Lesson: Knapsack and longest common subsequence →