[RMI18] Password

문제 : https://oj.uz/problem/view/RMI18_password

 

---

문제설명

 

길이가 최대 5000인 비밀번호 P가 있다.

P는 알파벳 소문자 a부터 시작해서, S번째 소문자까지 들로만 구성되어 있다.

 

예를들어, S가 4라면 비밀번호는 a,b,c,d 네 종류의 소문자로 이루어져 있다.

 

P의 길이 N과 S가 주어졌을 때, 주어진 쿼리를 이용하여 P를 찾는 문제이다.

 

---

사용가능한 함수

int query(string Q)

쿼리는 길이가 N이하인 문자열 Q를 인자로 받는다.

P의 부분문자열이면서, Q의 부분문자열인 것들 중 길이가 가장 긴 부분문자열의 길이를 반환하는 함수다.

 

아래는 P="aab"일 때, 예시이다.

Call	Return value
query("ab")	2
query("abb")	2
query("bab")	1
query("aab")	3

 

---

만점기준 제약사항

• N은 최대 5000, S는 최대 20
• 쿼리는 최대 50000번 호출 가능

 

---

풀이

우선 각 알파벳의 빈도수부터 구해보자

 

길이가 N이고 소문자 a로만 이루어진 Q를 쿼리 인자로 주었을 때,

이 때 쿼리의 반환값이 P에서의 a의 개수가 된다.

 

이제 cnt[X]를 P에서의 문자 X의 개수라고 하자

S번의 쿼리로 cnt[X]를 모두 구할 수 있다.

---

 

cnt[]와 쿼리로 이제 두 문자열의 순서를 구해보자

cnt[a]=3, cnt[b]=4라고 예시를 들어보자

 

aaa와 bbbb 두 문자열이 있고, Q=abbbb로 쿼리를 수행해보자

이 때, 만약 쿼리의 반환값이 4보다 크다면, bbbb의 앞에는 a가 적어도 하나는 존재한다는 것을 알 수 있다.

prefix=a로 정의하자

 

prefix는 P에서 a와 b로만 이루어진 부분문자열을 찾아내어 갱신해나갈 변수다.

 

 

다음으로 aaa와 bbbb에서 Q=aabbbb로 쿼리를 수행해보자

만약 쿼리의 반환값이 4+1보다 크다면, bbbb의 앞과 prefix 사이에는 a가 존재한다.

prefix=aa가 되었다.

 

 

다음으로 aaa와 bbbb에서 Q=aaabbbb로 쿼리를 수행해보자

이번에는 쿼리의 반환값이 4+2가 나왔다고 가정해보자

그러면 bbbb의 앞과 prefix 사이에는 a가 존재하지 않는다.

prefix=aab가 되었다.

 

 

다음으로 aaa와 bbbb에서 Q=aababbb로 쿼리를 수행해보자

쿼리의 반환값이 3+3보다 크다면, bbb의 앞과 prefix사이에는 a가 하나이상 존재한다.

prefix=aaba가 되었다.

 

이러한 방법으로 prefix를 추가해나가면, a와 b로만 이루어진 P의 부분문자열을 찾을 수 있다.

이 때 사용한 쿼리 수는 \(O(cnt[a]+cnt[b])\)이다.

---

 

마지막으로 a,b로만 이루어진 부분문자열 X와

c,d로 이루어진 부분문자열 Y도 보자.

로직은 a,b를 구할 때와 똑같다.

 

X=aababbb, Y=dcdc라 할 때, Q=adcdc로 쿼리를 수행해보자

반환값이 4보다 크다면, Y앞에는 a가 적어도 하나 있다는 것이고, 이 때 prefix는 a가 된다.

반환값이 4와 같아면, Y앞에는 a가 오지 않는다는 것이고, 이 때 prefix는 d가 된다.

 

\(O(len(X)+len(Y))\)번의 쿼리로 a,b,c,d로 이루어진 부분문자열을 구하였다.

 

---

 

알파벳 소문자를 두 개씩 짝지어서 해나가여 최종 P를 구할 수 있게 되었다.

이는 분할정복으로 쉽게 구현할 수 있다.

쿼리의 전체 연산 복잡도는 \(O(S+NlogS)\)가 된다.

 

 

 

 

---