Longest common subsequence of two event logs

Question

Two systems each write an ordered log of order-state codes. Network hiccups drop some entries, so the logs differ, but the events that did land arrive in the same relative order in both. To measure how much they agree you want the longest common subsequence (LCS): the longest string of codes that appears in both, in order, not necessarily contiguously.

a = "ABCBDAB", b = "BDCAB"
-> 4            # e.g. "BCAB" appears in order in both

Return the length of the longest common subsequence. Target $O(|a|\cdot|b|)$ time and $O(\min(|a|,|b|))$ space.

Accepted Answer

Let L[i][j] be the LCS length of the first i characters of a and the first j of b. Boundaries are all zero (an empty prefix shares nothing). For a general cell, look at the last characters: L[i][j] = \begin{cases} L[i-1][j-1] + 1 & ai = bj \ \max\big(L[i-1][j],\ L[i][j-1]\big) & 	ext{otherwise} \end{cases} If the last characters match, extend the best alignment of the shorter prefixes by one. If they do not, the shared symbols cannot use both, so throw away one character and take the better of the two options. Each row depends only on the previous one, so roll two rows: For "ABCBDAB" vs "BD…

Longest common subsequence of two event logs

Your answer

More Coding questions