Brute-force Algorithm (Longest Common Subsequence)

Definition

Brute-force Algorithm (Longest Common Subsequence)

Given two strings and , the brute-force algorithm for the longest common subsequence problem enumerates every choice of positions in , tests whether the resulting subsequence also occurs in , and returns the greatest accepted length:

There are choices of positions: each position is either retained or omitted. Different choices can produce the same string when letters repeat.

Pseudocode

lcs_bruteforce(S, T):
    if |S| > |T|:
        swap(S, T)
    best := 0
    for each subset I of {0, ..., |S|-1}:
        A := letters S[i] for i in I, in increasing index order
        if is_subsequence(A, T):
            best := max(best, |A|)
    return best
 
is_subsequence(A, T):
    next := 0
    for each letter c in T:
        if next < |A| and A[next] == c:
            next := next + 1
    return next == |A|

The subsequence test matches each letter of at its earliest available position in . Choosing an earlier match leaves at least as much of available for the remaining letters.

Correctness

Exact LCS Length

The algorithm returns the length of a longest common subsequence of and .

Proof

After each iteration, best is the greatest length among the common subsequences examined so far.

No overestimate: every accepted string is a subsequence of by construction and of by the test. Thus best cannot exceed the optimum.

No underestimate: every common subsequence is realised by some choice of positions in . In particular, the enumeration reaches a longest one and accepts it. Thus the final best is at least the optimum.

Together, these bounds give equality. If no non-empty common subsequence exists, the empty subsequence supplies the correct answer .

Complexity

After swapping inputs if necessary, assume . Constructing each candidate costs and checking it costs , including empty inputs. Therefore,

For non-empty , this is time. Generating one candidate at a time uses auxiliary space; storing all candidates is unnecessary.

Examples

Enumerating subsequences of abc

Let and . Without swapping the inputs, the eight candidates are

Only are subsequences of . Hence the answer is . Swapping the inputs reduces the enumeration to the four subsequences of and gives the same answer.