거의 LCS만큼

0과 1로만 이루어진 문자열을 이진 문자열이라고 하자. 어떤 이진 문자열에서 원소 몇 개를 골라 원래 순서를 유지한 채 이어 붙인 것을 그 문자열의 부분수열이라고 한다. 예를 들어 010의 비어 있지 않은 부분수열은 0, 1, 00, 01, 10, 010이다.

두 이진 문자열의 공통 부분수열은 두 문자열 모두의 부분수열인 문자열이다. 예를 들어 101과 011의 비어 있지 않은 공통 부분수열은 0, 1, 01, 11이다. 두 문자열 $C_1$, $C_2$의 가장 긴 공통 부분수열의 길이를 $\mathrm{LCS}(C_1, C_2)$라고 쓴다. 예를 들어 101과 011의 가장 긴 공통 부분수열은 11 또는 01이므로 $\mathrm{LCS}(101, 011) = 2$이다.

가장 긴 공통 부분수열의 길이를 정확히 구하는 것은 비용이 크다. 그래서 여기서는 형태가 단순한 공통 부분수열만 다룬다. 어떤 이진 문자열이 단조(monotone) 문자열이라는 것은 그 문자열이 $0^a 1^b$ 또는 $1^a 0^b$ 꼴, 즉 (같은 문자로만 이루어진 문자열을 특수한 경우로 포함하여) 0으로 이루어진 한 덩어리 뒤에 1로 이루어진 한 덩어리가 오거나 그 반대인 경우를 말한다.

두 이진 문자열 $C_1$, $C_2$가 주어질 때, 두 문자열의 공통 부분수열 중 단조 문자열인 것의 최대 길이 $k$를 구하여라. 이 값은 항상 $2k > \mathrm{LCS}(C_1, C_2)$를 만족함이 알려져 있어, 빠르게 계산할 수 있는 좋은 근삿값이 된다.

첫째 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어진다 ($1 \le n, m \le 100000$). 둘째 줄에 길이 $n$인 이진 문자열 $C_1$이, 셋째 줄에 길이 $m$인 이진 문자열 $C_2$가 주어진다.

$C_1$과 $C_2$의 공통 부분수열 중 단조 문자열($0^a 1^b$ 또는 $1^a 0^b$ 꼴)인 것의 최대 길이를 정수 하나로 한 줄에 출력한다. 두 문자열에 공통으로 나타나는 문자가 적어도 하나 있다고 가정해도 좋다. 즉 답은 항상 1 이상이다.

단조 공통 부분수열의 최대 길이는 다음 두 값 중 큰 쪽이다. 하나는 같은 문자로만 이루어진 최대 공통 런의 길이(0의 개수는 두 문자열의 0 개수 중 작은 값, 1도 마찬가지)이고, 다른 하나는 0 덩어리 뒤 1 덩어리 또는 1 덩어리 뒤 0 덩어리 꼴의 최대 공통 길이이다. 앞쪽 문자를 $i$개 고른 뒤 그 뒤에 남는 반대 문자의 개수를 두 문자열에서 각각 세어 최댓값을 취하면 $O(n+m)$에 계산할 수 있다.