https://www.acmicpc.net/problem/20191
문제 요약
- 문자열 S와 T가 주어짐
- "줄임말"의 정의가 있음
- T를 n번 반복한 문자열이 있고, S가 그 문자열의 줄임말이 될 때 이를 만족하는 n의 최소값
- N : S의 길이, 100만
- M : T의 길이, 10만
접근법
- 어떻게 이어붙이고 판단하는가를 생각하기가 어려웠음
- 일단 S는 T의 가장 앞에서부터 매칭하는 것이 유리하다고 판단함(그리디) => 가장 앞에 것에 매칭해도 일단 손해는 안봄
- S에 등장하는 문자별로 일일이 판단을 하면.. 최악의 경우 N x M의 시간이 걸림 : 문자별로 훑는데 걸리는시간(=M) x 문자의 개수(= N)
- 문자별로 바로 다음 위치를 판단하면 좋겠는데
- 문자별 : T에서 문자별로 등장하는 위치를 모아놓는다
- 다음위치 판단 : x의 다음에 있는 가장 작은 원소...lower_bound!
구현
- T를 탐색하면서 문자별로 인덱스를 모아놓는다
- T에서 어느위치부터 매칭하면 되는지 값을 갖고 다닌다 ==> cur
- S를 탐색하면서 S의 문자열 + cur의 조합으로 다음번 가장 적절한 위치를 구한다
- 구하는 위치가 cur보다 작으면 => T를 하나 더 붙임
DP 접근법
- 난이도 기여에서 dp[i][c] = "현재 포인터가 i에 있고 글자 c를 찾으려고 할 때 다음 포인터의 위치"를 한참 이해했음
- lower_bound를 배열상으로 펼쳐서(?) 표현하면 됨
- 예를 들어 a가 나타나는 위치가 0, 3, 5, 7이라고 하면
- [0, 3, 3, 3, 5, 5, 7, 7, 0] 이런식으로 가장 가까운 위치를 표현해주고, 가장 끝 위치 이후자리는 알아서 처리함
- 저런 배열을 [10만][a ~ z ] 개 갖고 있으면 됨
newbieski