Almost LCS

Call a string made up only of the characters 0 and 1 a binary string. A subsequence of a binary string is obtained by picking some of its characters and keeping their original order. For example, the non-empty subsequences of 010 are 0, 1, 00, 01, 10, and 010.

A common subsequence of two binary strings is a string that is a subsequence of both. For example, the non-empty common subsequences of 101 and 011 are 0, 1, 01, and 11. Let $\mathrm{LCS}(C_1, C_2)$ denote the length of a longest common subsequence of $C_1$ and $C_2$. For instance, a longest common subsequence of 101 and 011 is 11 or 01, so $\mathrm{LCS}(101, 011) = 2$.

Computing the exact length of a longest common subsequence is expensive, so here we restrict attention to common subsequences of a simple shape. Call a binary string monotone if it has the form $0^a 1^b$ or $1^a 0^b$: a block of zeros followed by a block of ones, or the reverse (strings of a single repeated character are the special case where one block is empty).

Given two binary strings $C_1$ and $C_2$, find the maximum length $k$ of a common subsequence of $C_1$ and $C_2$ that is monotone. It is known that this value always satisfies $2k > \mathrm{LCS}(C_1, C_2)$, so it is a good, quickly computable approximation.

The first line contains two integers $n$ and $m$ separated by a single space ($1 \le n, m \le 100000$). The second line contains a binary string $C_1$ of length $n$, and the third line contains a binary string $C_2$ of length $m$.

Print a single integer on one line: the maximum length of a common subsequence of $C_1$ and $C_2$ that is monotone (of the form $0^a 1^b$ or $1^a 0^b$). You may assume that at least one character is common to both strings, so the answer is always at least 1.

The longest monotone common subsequence is the larger of two quantities: the longest common run of a single repeated character (the number of shared zeros is the smaller of the two zero counts, and likewise for ones), and the longest common subsequence of the shape zeros-then-ones or ones-then-zeros. Fixing how many leading characters you take and then counting the opposite character remaining after them in each string yields an $O(n+m)$ algorithm.