2월 4주차 PS: 문자열

대신

귀

여운

문자열을

드리겟

습니다

 

문자열은 마법처럼 풀리는 게 많아서 재밌다. 응용도 내가 푸는 레벨에서는 심하지 않고..

백준 13506 카멜레온 부분 문자열

www.acmicpc.net/problem/13506

13506번: 카멜레온 부분 문자열

학교 수업에서 본 문제인데, 근본 살리기를 위해 재방문 해 보았다.

 

풀이>>

주요 아이디어: KMP

중간에 한번 더 나오는 공통 접두-접미사들 중 제일 긴 걸 찾으라는 말이다. 원래 문자열을 $a$라 하자.

 

$fail(x)$는 문자열 $a[0:x]$의 최대 공통 접두-접미사의 길이이다.

노란색 부분의 길이가 $fail(N-1)$이다.

파란색도 공통 접두-접미사이다.

이런 느낌으로, 길이가 $fail(N-1)$보다 작은 공통 접두-접미사가 있다면, 그 부분 문자열은 $a[0:fail(N-1)-1]$의 공통 접두-접미사이기도 하다. 약간 최대공약수-약수 느낌?

그러면 모든 공통 접두-접미사의 길이는 $fail(N-1)$, $fail(fail(N-1)-1)$, $fail(fail(fail(N-1)-1)-1)$, ...이 된다.

 

그리고, 위 그림에서 보이듯이, 길이가 $fail(N-1)$인 부분 문자열을 제외하면 전부 중간에 한번 더 나올 수밖에 없다.

투명한 파란색 직사각형을 보면 이해가 될 것이다. (심지어 두 번 나옴)

 

결론적으로.. 길이 $fail(N-1)$짜리 문자열이 중간에 한 번 더 나오는지만 KMP로 체크해주면 답을 알 수 있다.

 

시간복잡도는 $O(N)$이다.

 

백준 2401 최대 문자열 붙여넣기

www.acmicpc.net/problem/2401

2401번: 최대 문자열 붙여넣기

벡터가 생각보다 느려서 당황했다. 믿음의 제출을 하면 잘 맞는다.

 

풀이>>

주요 아이디어: DP, KMP

KMP는 이 문제에서 검색 셔틀일 뿐..

 

기초적인 DP 문제를 풀어 봤다면, 거의 피보나치 급의 쉬운 DP로 환원할 수 있다는 걸 알 수 있다.

붙여넣을 수 있다면 문자열 길이가 $l$일 때 $DP[i+l] + l$로 전이하면 된다.

붙여넣기가 애매하면 $DP[i+1]$로 전이하면 된다.

 

그런데, 문자열을 붙여 넣을 수 있는지를 판별하는 과정에서 문제가 생긴다. 매번 판별을 반복하다가는 시간복잡도가 $O(N^2)$가 되어 TLE를 피할 수 없다. 이걸 KMP를 이용한 전처리로 해결한다.

 

KMP를 문자열 개수만큼 써서 각 문자열이 나타나는 위치를 전부 저장한다.

DP가 그 위치에 도착하면 붙여 넣을 수 있게 하면 된다.

 

시간복잡도는 $O(NL)$이며, 상수가 아주 크진 않아서 생각보다 빠르게 통과한다.

 

백준 10747 Censoring

www.acmicpc.net/problem/10747

10747번: Censoring

드디어 이걸 풀 실력은 됐구나..를 느낀 문제

1년 전에 C99로 1등 먹은 친구가 있었는데, 보고 충격받았던 기억이 난다.

그런 친구들을 따라잡기 위해서 나름 열심히 하는 중이다.

 

풀이>>

주요 아이디어: KMP

검색하는 문자열을 $S$, 찾고자 하는 문자열을 $T$라 하자.

 

당연히 계속 돌면서 KMP를 쓰면 문제가 된다. 

여기서 한 가지 질문을 하자: Dynamic하게 KMP를 적용할 수는 없나?

 

답은 "가능" 이다. KMP는 진행 과정에서 이미 비교가 끝난 부분을 신경쓰지 않는다. 

$S$의 현재 자리에, $T$의 어떤 자리를 대응시켜야 할 지만 알면 된다.

그러니까, $S$의 비교가 끝난 부분들에 대해서, $T$의 어떤 자리와 비교했었는지를 모두 저장한다. 

 

그러면 KMP를 하는 과정에서 타겟 문자열이 나오면 전부 삭제해버리고, 과거의 상태로 롤백시켜서 거기서부터 KMP를 재시작해버릴 수 있게 된다. "어디까지" 롤백시킬지는 직접 써보면서 이해해 보자. 

 

KMP를 단 한번! 하기 때문에 시간복잡도는 $O(N)$이 된다.

 

백준 4206 피보나치 단어

www.acmicpc.net/problem/4206

4206번: 피보나치 단어

이런 변방에 이 정도 꿀문제가 숨겨져 있었다니..

 

풀이>>

주요 아이디어: DP, KMP

아이고, $F(100)$쯤 가면, 길이의 하한은 대충 $({{3}\over{2}})^{100}$쯤 된다. 여기서 KMP를 돌리는 건 말도 안 된다.

(*유클리드 호제법의 시간복잡도 증명 글 참고 ㅎㅎ)

 

되게 재밌는 문제다. 일단 관찰할 수 있는 건, 한 번 $p$가 등장하면 그 다음부터는 쭉쭉 등장한다는 것이다.

게다가, $F(N)$에서의 $p$의 개수는 대충 이전 두 항에서 등장한 $p$의 개수의 합과 같다.

 

대충을 정확한 값으로 바꾸기 위해서는, 합치는 과정에서 추가적으로 등장한 $p$의 개수도 세 줘야 한다. 그걸 효율적으로 하는 방법에 대해서 알아보자.

문자열을 합쳐보면, 우리가 세지 못한 경우는 $p$가 $F(N-1)$과 $F(N-2)$ 사이를 가로질러서 생기는 경우 뿐이다. 

$p$의 길이를 $M$이라 하자. $F(N-1)$의 오른쪽 $M-1$개 문자와 $F(N-2)$의 왼쪽 $M-1$개 문자를 뽑아다가 합쳐놓으면 "가로지르는" 길이 $M$짜리 문자열들이 그 안에 전부 들어 있게 된다. 이제 그 합쳐놓은 문자열에서 KMP를 돌려 $p$의 개수를 세 주면 된다. 

 

개수를 $c$라 하면 $DP[i] = DP[i-1]+DP[i-2]+c$가 된다. 이를 계산해주면 시간복잡도는 $O(NM)$정도가 된다.

 

PS는 너무 재밌다. 다만 내 끈기와 실력 모두가 부족해서 아쉽다.