문자열 대회 간략한 풀이

https://www.acmicpc.net/contest/view/218

이 대회의 간략한 풀이를 적고자 합니다. 자세한 알고리즘 및 자료구조 설명은 생략했습니다.

문자열로 나올 수 있는 여러 종류의 문제가 있어서 문자열 연습하기 좋은 대회라고 생각합니다.

오타, 지적 환영합니다.



A

13713번 문제: 문자열과 쿼리

hint. Hashing, Suffix Array, Z-Algorithm

  • $i$에 대해, $F(i)$는 원래 문자열과 $S[1...i]$의 공통 접미사 중 가장 긴 길이입니다.
  • $S[1...i]$$S[1...n]$의 길이 $x$짜리 접미사 두 개를 봅시다.
  • $x \le F(i)$라면 두 접미사가 같습니다.
  • $x \gt F(i)$라면 두 접미사가 다릅니다.
  • 따라서 x에 대해 이진 탐색을 하면 됩니다. 문자열 비교는 해싱으로 $O(1)$에 하면 됩니다.
  • Suffix Array를 사용한 풀이도 있습니다.
  • 위 두 알고리즘 모두 $O(N log N)$입니다. 반면 Z-Algorithm을 쓰면 $O(N)$이 가능하다고 합니다. ( http://codeforces.com/blog/entry/3107 )



B

13438번 문제: 계단 오르기 운동

hint. DP, Automata





  • $i$개의 문자를 썼을 때, 주어진 문자열의 $j$번 까지 매칭이 되었고, 현재 $H_i = k$인 경우의 수를 구합니다. $H_i$$i$개 중 $U$의 개수 - $L$의 개수입니다.

  • 3차원 다이나믹으로 $O(N^3)$입니다.



C

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

hint. KMP





  • 문자열의 길이를 $N$, 실패 함수를 $fail(i)$라고 합시다.
  • 접두사와 접미사가 둘 다 되는 문자열 중 가장 긴 것은 당연히 $N$입니다.
  • 두 번째로 긴 것은 $fail(N)$입니다. (정의에 의해)
  • 세 번째로 긴 것은? $fail(fail(N))$입니다.
  • 이렇게 0보다 큰 동안 계속 내려가면, 접두사와 접미사가 모두 되는 문자열들을 찾을 수 있습니다.
  • 그들 중, 접두사와 접미사를 제외하고 최소 한번 더 나타나는 문자열들을 찾으면 됩니다.
  • 한번 더 나타난다는 것은, 길이가 $N$이 되기 전에 이미 한 번 (접두사와 접미사가 모두 되는 문자열)이었다는 것입니다.
  • 따라서 $1 \le x \le N-1$에 대해, 길이 $fail(x)$인 접두사는 접미사가 아니면서도 한 번 더 나오게 됩니다.



D

13576번 문제: Prefix와 Suffix

hint. KMP, Suffix Array, LCP





  • C번의 아이디어로, 길이들은 구할 수 있습니다.
  • 등장 횟수는 LCP Array를 사용해서 구할 수 있습니다.



E

12104번 문제: 순환 순열

hint. KMP





  • $A[n] = A[0], A[n+1] = A[1], ... $이렇게 A를 확장시켜 봅시다.
  • $B$를 순환시키지 않는다면, $A[0...(n-1)]$$B[0...(n-1)]$이 같은지 확인하면 됩니다.
  • $B$를 한 번 순환시킨다면, $A[1...(n)]$$B[0...(n-1)]$이 같은지 확인하면 됩니다.
  • $B$를 두 번 순환시킨다면, $A[2...(n+1)]$$B[0...(n-1)]$이 같은지 확인하면 됩니다.
    ...
  • $B$$n-1$번 순환시킨다면, $A[(n-1)...(2n-2)]$$B[0...(n-1)]$이 같은지 확인하면 됩니다.
  • 즉, $A[0...(2n-2)]$에서 $B[0...(n-1)]$가 등장하는 횟수가 답이 됩니다.
  • KMP를 사용하여 구하면 됩니다.



F

12105번 문제: 123456789 찾기

hint. KMP, DP





  • 일단 KMP를 사용해서, 등장할 수 있는 수들을 모두 구할 수 있습니다.
  • 이들 중 수들을 적당히 뽑아, 1부터 9까지로 나누어 떨어지게 하면 됩니다.
  • 1부터 9까지 나누어 떨어지려면, 다음 4가지 조건을 만족하면 됩니다.
  • 2의 지수가 3 이상. 3의 지수가 2 이상. 5의 지수가 1 이상. 7의 지수가 1 이상.
  • 어떤 수 $X$$X = 2^a 3^b 5^c 7^d A$ 라고 했을 때, $(a, b, c, d)$로 상태를 만들 수 있습니다. $A$$2, 3, 5, 7$로 나누어 떨어지지 않는 수입니다.
  • 이 때, 우리는 2의 지수가 3인지, 4인지, 그 이상인지는 관심이 없습니다. 이들은 그냥 모두 3이라고 해도 됩니다.
  • 따라서 $(min(a, 3), min(b, 2), min(c, 1), min(d, 1))$로 상태를 만들면, $4 \times 3 \times 2 \times 2$개의 상태가 만들어집니다.
  • 등장할 수 있는 수들을 $P[1...m]$이라 하면, $i(i \le m)$번까지 결정한 후 $j$번 상태인 경우의 수를 DP를 사용해 구할 수 있습니다.



G

12939번 문제: 부분 문자열

hint. Aho-Corasick, DP





  • 아호 코라식 알고리즘을 알아야 풀 수 있는 문제입니다.
  • 트라이를 만들고 상태 전이를 구현합니다.
  • 이 때, 각 상태마다 각 문자열이 들어 있는지 모두 알아 놓아야 합니다.
  • 어떤 문자열을 만들었을 때, $N$개 중 무엇이 부분문자열로 포함되어 있는지를 알려면 $2^N$개의 상태가 필요합니다.
  • 길이 $i$를 만들었을 때, 트라이 위 상태가 $j$이고, $N$개 중 부분문자열이 $k(0 \le k \lt 2^N)$ 조합으로 들어 있는 경우의 수를 DP를 사용해 구합니다.
  • 시간 복잡도는 $O(L \times \sum L_i \times 2^N \times 26)$입니다. $L_i$는 주어진 $N$개 중 $i$번째 문자열의 길이입니다.



H

12106번 문제: 부분 문자열의 개수

hint. DP





  • G번에서 훨씬 쉬워진 문제입니다. 문자열 하나에서 아호 코라식을 써서 풀어도 됩니다.
  • B번처럼 풀어도 됩니다. 길이 $i$짜리를 만들었을 때, $S$$j$번째 문자까지 맞는 경우의 수를 DP를 사용해 구합니다.



I

14444번 문제: 가장 긴 팰린드롬 부분 문자열

hint. Manacher's Algorithm





  • Manacher's Algorithm은 이 문제를 $O(N)$에 해결하는 알고리즘입니다.
  • 해싱 및 이진 탐색을 이용해서 $O(N logN)$에 해결할 수도 있습니다.



J

13432번 문제: 좋은 부분 문자열

hint. Suffix Array, Parametric Search





  • 더 좋은 풀이가 있는 것 같지만, 제 풀이라도 설명드리겠습니다.
  • 먼저 Suffix Array와 LCP Array를 구합니다. 이들을 각각 $SA[i]$, $LCP[i]$라고 하겠습니다.
  • $LCP[i]$$i$번째 접미사와 $i-1$번째 접미사의 공통 접두사 길이입니다.
  • 부분문자열 중 사전편집상 빠른 것부터 봅시다.
  • 중복되는 문자열은 한 번만 세어야 합니다. 따라서, $SA[i]$로 시작하는 문자열을 볼 때는 길이가 $LCP[i]$ 이하인 것들은 볼 필요가 없습니다. 이것들은 $SA[i-1]$로 시작하는 것을 처리할 때, 혹은 그 전에 처리합니다.
  • $SA[i]$로 시작하는 문자열을 볼 때 길이는 $LCP[i] + 1$부터 $N - SA[i]$까지 가능합니다. 길이가 $N - SA[i]$일 경우 문자열 $S$의 끝까지 포함하는 부분문자열입니다.
  • 이들 사이에서 parametric search를 사용합니다.
  • 길이 $x$의 가능 여부는 아래와 같이 확인합니다.
  • $i$와 LCP 거리가 $x$ 이상인 인덱스들을 $[L, R]$이라고 합시다. 이 두 값은 LCP Array를 sparse table로 구현했을 경우 쉽게 구할 수 있습니다.
  • $SA[L], SA[L+1], ..., SA[R]$$SA[i]$와의 절댓값 차이가 $x$이상인 값이 있으면, 이는 가능합니다. 시작점이 서로 $x$ 이상 떨어져 있으면서 길이 $x$가 같기 때문입니다.
  • $SA[L], SA[L+1], ..., SA[R]$ 중 최댓값 및 최솟값만 확인해도 됩니다.
  • $SA[L...R]$의 최댓값 및 최솟값은 인덱스트리 등을 사용해서 구할 수 있습니다.
  • 따라서 답을 구할 수 있습니다. 시간 복잡도는 $O(N log^2 N)$입니다.






댓글 (5개) 댓글 쓰기


qja0950 7년 전

cki님 너무 멋져요..!


cki86201 7년 전

qja0950님 너무 귀여워요..!


h0ngjun7 7년 전

두 분 다 너무 멋지고 귀여워요..!


cbs0615 6년 전

14444번 LPS문제를 O(n log n)만에 푸는 방법을 조금만 가르쳐주실수 있나요?


onjo0127 6년 전

답을 X라고 정하고 X를 이분탐색하면 됩니다. X/2 길이의 모든 구간을 해싱하고, 문자열을 뒤집어서 똑같이 X/2 길이의 모든 구간을 해싱합니다. 이때 어떤 위치 k를 기준으로 같은 해시값이 존재한다면, k가 중심인 길이 X의 팰린드롬이 존재한다는 말이 됩니다. 이때 답은 X보다 크거나 같을 것입니다. 만약 그런 팰린드롬이 존재하지 않는다면, 답이 X보다 작다는 말이 되겠지요. 이렇게 풀면 O(N log N)에 문제를 해결할 수 있습니다. :)