Informatica Online Judge

  사투리 [0813 / 032D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 125   Total Tried : 176


The Champion of this Problem (C++) : gs17018 - ms / 350byte
My Best Submission (C++) : N/A

[]

Background

GSHS의 K모씨는 서울에서 태어났음에도 불구하고 대구에서 자라났기 때문에 사투리를 사용한다.

이 때문에 학교친구들은 K모씨에게 장난을 칠 때 사투리로 장난을 치는데 K모씨는 사투리와 서울말이 그렇게 다르지 않다는 것을 친구들에게 알리고 싶다.

그래서 K모씨는 주어진 사투리와 서울말의 subsequence(연속되는 부분 순서)의 최대 값을 구하려 한다.

이를 구하는 프로그램을 작성하시오.

* 참고 : subsequence란 원래 순서에서 일부 몇 개를 지운 순서를 의미한다.

예를 들어 abcdefg 라는 순서가 있다면 이 순서의 부분순서는

abcdefg, adeg, efg, ag 등이 있다.

하지만 ba와 같이 순서가 바뀐 것은 부분순서가 아니다.

그리고, abcde, bace 의 최대 공통 부분순서는
ace 또는 bce 가 된다. 따라서 위 두 순서의 최대 공통 부분순서의 길이는 3이다.

Input

첫 줄에 길이가 N이하인 사투리가 공백 없이 주어진다.
둘째 줄에 길이가 N이하인 서울말이 공백 없이주어진다.
(사투리와 서울말은 모두 알파벳으로 이루어져 있다)

[입력값의 정의역]
1 <= N <= 1000

Output

공통부분순서의 최대 길이를 출력하라.

IO Example

입력
sicohwkdfjxo
wocibhxs

출력
3

* 설명
sic oh wkdfj x o
w o cib hx s

와 같이 ohx가 길이가 3인 공통부분순서 중 하나이다. 이보다 더 긴 공통부분순서는 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]