Informatica Online Judge

  Longest Prefix (가장 긴 접두어, IOI-96) [0279 / 0117]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

일부 생물학적인 객체의 구조는 성분의 각 자리가 대문자로 표현된 서열의 형태로 표현된다.

생물학자들은 매우 긴 서열을 필수성분이라고 불리는 짧은 서열로 분해하는 것에 흥미를 가진다.

서열 S는 주어진 필수성분 집합 P로 부터 구성될 수 있다. 그리고 주어진 필수성분을 모두 사용할 필요는 없다. 예를 들어 서열 "ABABACABAAB"는 다음 필수성분으로 부터 만들어 질 수 있다.

{A, AB, BA, CA, BBC}

S의 첫번째 K개의 문자들은 S의 길이가 K인 접두어라고 부른다.

입력으로 필수성분을 구성하는 집합 P 및 어떤 서열 S의 정보가 주어질 때 주어진 필수성분으로 부터 만들어 질 수 있는 가장 긴 S의 접두어의 길이를 구하는 프로그램을 작성하시오.

Input

먼저 200개 이하로 구성된 필수성분의 집합 P가 주어진다. 필수성분의 길이는 10을 넘지 않으며 모두 대문자로 구성된다.

필수성분의 집합의 종료는 "."로 나타낸다.

같은 필수 성분이 중복되어 주어지는 경우는 없다.

다음으로 길이가 20만 이하인 서열 S가 주어진다. 길이가 76이상일 경우에는 줄이 바뀔 수 있으며 줄바꿈 문자(엔터)는 서열의 부분이 아니므로 입력에 주의한다.

Output

주어진 정보로 만들 수 있는 가장 긴 접두어의 길이를 출력한다.

IO Example

입력
A AB BA CA BBC
.
ABABACABAABC

출력
11

설명 : 서열 S중 집합 P의 요소로 만들어 질 수 있는 접두어는 "ABABACABAAB"이다. 마지막 "C" P의 원소로는 만들 수 없으므로 길이는 11이다.

IOI(International Olympiad in Informatics) - 96 기출

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