최대공통부분문자열 |
---|
한 문자열의 부분 문자열이란 문자열에서 임의의 문자들의 순서를 바꾸지 않고 원래대로 이어 만든 문자열이다. 예를 들어, 문자열 abc의 부분 문자열 a, ab, abc, b, bc, c 이렇게 여섯 가지가 있다. 두 문자열 A와 B가 주어질 때 A와 B의 공통 부분 문자열 중 가장 길이가 긴 것을 찾아 그 문자열의 길이를 출력하는 프로그램을 작성하시오. 예를 들어, television 과 telephones, 이렇게 두 개의 문자열이 주어진 경우 둘의 공통 부분 문자열은 teon, teles, teleon 등 여러 가지가 있고, 그 중 길이가 가장 긴 것은 teleon 이며, 그 길이는 6이다. |
입력 | |
---|---|
첫째 줄에는 문자열 A의 길이 n(<=10,000)이 주어지고, 둘째 줄에는 문자열 A가 주어진다. 셋째 줄에는 문자열 B의 길이 m(<=10,000)이 주어지고, 넷째 줄에는 문자열 B가 주어진다. |
출력 | |
---|---|
첫째 줄에 가장 긴 공통 부분 문자열의 길이를 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 10 television 10 telephones | |
출력 | 6 |