CodeDrive

문제:

어떤 원본 문자열 S가 주어졌을 때, 이 문자열의 부분을 복사하여 P라는 새로운 문자열을 만들려고 한다. 복사를 할 때에는 copy(s, p) 이라는 함수를 이용하는데, 이는 S의 s번 문자부터 p개의 문자를 P에 복사해서 붙인다는 의미이다.

예를 들어 S="abaabba", P="aaabbbabbbaaa"인 경우를 생각해 보자. 이때는 copy(3, 2), copy(4, 3), copy(2, 2), copy(5, 2), copy(2, 3), copy(1, 1) 를 수행하여 P를 만들 수 있다. 각 단계별로 P는 "aa", "aaabb", "aaabbba", …와 같이 변하게 된다.

이와 같은 copy 연산을 이용하여 S에서 P를 만들려고 하는데, 이때 가능하면 copy 함수를 조금 사용하려고 한다.

S와 P가 주어졌을 때, 필요한 copy 함수의 최소 사용횟수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수 없는 경우는 입력으로 주어지지 않는다고 가정하자. 각 문자열은 최소한 한 개의 문자로 이루어져 있다.

출력:

첫째 줄에 copy 함수의 최소 사용횟수를 출력한다.

풀이방법:

 P에 있는 부분 문자열을 S에서 그리디하게 찾아내어 이 문제를 해결하도록 한다.

찾으려는 P의 문자를 S에서 찾은 뒤에 그 지점으로부터 얼마나 많이 일치하는지 확인한다. 예를 들어 S="abaabba", P="aaabbbabbbaaa" 일 때, P의 첫 문자는 'a'이며, S에서는 a가 0, 2, 3, 6 번째에 위치하고 있다. python의 find 함수를 이용하여 a의 위치를 확인하고, P와 S 에서 동시에 포인터를 이동하며 얼마나 많이 일치하는지 찾는다. 다음 탐색은 일치하는 수 만큼 P의 포인터를 이동시킨다. 이 경우에는 S의 2번째에서 aa가 가장 길게 일치하므로, P의 2번째 인덱스부터 다음 탐색을 시작한다.

문제링크:

https://www.acmicpc.net/problem/2195