PS하는 kdy

이번에는 지난 글에서 구현하는 방법을 알아본 접미사 배열과 lcp 배열을 어떻게 활용하는지 알아볼 것이다.문제를 풀어보기 전에는 suffix array와 lcp array가 도대체 어떤 의미를 가지나.. 싶기도 한데, 우리는 보통 접두사, 접미사보다도 부분 문자열에 관련된 문제를 많이 해결하게 된다. 이때, 우리가 주목해서 기억해야 하는 것은 부분 문자열은 결국 접미사의 접두사라는 것이다. 그러면 suffix array를 구했고, suffix array에서 lcp를 구한 것은 공통된 접미사의 접두사, 즉 공통된 부분 문자열에 관한 정보를 얻었음을 의미한다. https://www.acmicpc.net/problem/1605이 문제는 지난번 라빈 카프를 설명했을 때에도 다루었던 문제로, 부분 문자열 내에서 ..

이번에 다뤄볼 알고리즘은 해싱, 그 중에서도 라빈 카프 방식에 대해 살펴볼 것이다. 서론은 짧게 하고 빠르게 본론으로 넘어가보자.해싱 (Hashing)해싱은 문자열을 해시 함수에 넣어서 특정한 값으로 추출하는 것을 의미한다. 이때 가장 중요한 것은 같은 문자열을 같은 해시 함수에 여러 번 넣어 추출한 결과는 일정해야 한다는 점이다. 해싱을 하면 어떤 부분이 좋을까? 바로 비교 시간복잡도를 줄일 수 있다. "abcba"라는 문자열과 "abcbd"라는 문자열이 서로 같은지 다른지 비교하려고 한다. 일반적으로는 문자열의 가장 앞부터 비교하면서 5번째 문자까지 비교했을 때 비로소 두 문자열이 다르다는 것을 판단할 수 있다. 하지만 해싱을 이용해서 미리 두 문자열에 대해 정수 형태로 값이 나오는 해시 함수 결괏값..

이번에 글을 적어볼 알고리즘은 매내처 알고리즘이다. 이 역시 바로 본론으로 들어가자면, 매내처 알고리즘은 어떤 문자열 $S$가 주어졌을 때, $S$의 부분 문자열 (앞뒤에서 0개 이상의 문자를 떼어내 만들 수 있는 문자열) 중 팰린드롬인 것을 빠르게 탐색하는 알고리즘이다. 그리고 실제 구현은 Z 알고리즘과 비슷하게 이루어진다. Manacher 알고리즘은 부분 문자열 중 팰린드롬을 팰린드롬의 중심을 기준으로 탐색한다. 예시를 들어서 설명하자면, 팰린드롬 abcba의 중심은 c이고, abcba가 팰린드롬임을 알면 중심을 기준으로 대칭인 c, bcb가 팰린드롬이라는 사실을 이용할 수 있는 것이다. 이때 위 팰린드롬의 반경은 $2$이다. 왜냐하면 c를 중심으로 오른쪽으로 두 칸, 왼쪽으로 두 칸이 서로 대칭이라..

지난번에 다루었던 KMP 알고리즘에 이어서, 이번에는 Z 알고리즘에 대해 다뤄보고자 한다. 바로 본론으로 들어가보자. Z 알고리즘은 문자열 $S$가 주어졌을 때, 문자열 $S$의 접미사와 문자열 $S$의 최대 공통 접두사의 길이를 빠르게 구하는 알고리즘이다. 예시를 들면 아래와 같다. 위 표와 같이 $Z[i]$에 $i$번째 문자로 시작하는 접미사와 원본 문자열의 공통 접두사의 최대 길이를 저장하는 알고리즘이 Z 알고리즘이고, Z 알고리즘으로 구한 이 array를 보통 Z array라고 부른다. 이 역시 Naive하게 구현하면 문자열의 길이가 $N$일 때 $O(N^2)$이 소요된다. Z 알고리즘은 이때 불필요한 탐색을 최적화하여 시간복잡도를 $O(N)$으로 줄인다. 그 원리는 아래와 같다. idx ..