ABC

시간 제한1초메모리 제한128 MB

요약

a, b, c로 이루어진 두 문자열의 공통 부분수열 중 알파벳 순서로 감소하지 않는 것의 최대 길이를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 누적 합
정답자: 아직 제출이 없습니다

문제

소문자 'a', 'b', 'c'로만 이루어진 두 문자열 $X$ 와 $Y$ 가 주어진다. $X$ 와 $Y$ 의 가장 긴 비내림차순 공통 부분 수열의 길이를 구하라. 즉, 다음 두 조건을 모두 만족하는 가장 긴 수열을 찾으면 된다.

$X$ 의 부분 수열이면서 동시에 $Y$ 의 부분 수열이다. 다시 말해 $X$ 와 $Y$ 에서 각각 글자 몇 개(0개일 수도 있다)를 지워서 만들 수 있다.
알파벳 순서로 비내림차순이다. 즉 어떤 글자 $v$ 의 앞에는 $v$ 보다 알파벳에서 뒤에 오는(아스키 코드가 더 큰) 글자가 나오지 않는다. 세 글자의 순서는 $a < b < c$ 이다.

입력

첫째 줄에 두 문자열 $X$ 와 $Y$ 의 길이를 나타내는 두 정수 $n$ 과 $m$ 이 주어진다 ( $1 \le n, m \le 200000$ ). 둘째 줄에 문자열 $X$ 가, 셋째 줄에 문자열 $Y$ 가 주어진다. 두 문자열은 모두 소문자 'a', 'b', 'c'로만 이루어져 있다.

출력

조건을 만족하는 가장 긴 수열의 길이를 첫째 줄에 출력한다.

힌트

예제 입력에서 조건을 만족하는 가장 긴 수열은 "abc"이며, 그 길이는 $3$ 이다.

예제7

예제 1
입력
```
5 6
cabbc
bacbcc
```
예상 출력
```
3
```
예제 2
입력
```
1 1
a
a
```
예상 출력
```
1
```
예제 3
입력
```
1 1
a
c
```
예상 출력
```
0
```
예제 4
입력
```
4 3
aaaa
aaa
```
예상 출력
```
3
```
예제 5
입력
```
3 3
abc
abc
```
예상 출력
```
3
```
예제 6
입력
```
3 3
abc
cba
```
예상 출력
```
1
```
예제 7
입력
```
6 6
aabbcc
aabbcc
```
예상 출력
```
6
```