-
Run Enumerate로 문제를 풀어보자
이 포스트는 Run Enumerate의 구현 및 활용에 대해 다루며, koosaga님의 포스트를 기반으로 쓰여졌습니다. 이 글에서는 Run Enumerate를 문제 풀이에 활용하는 방법을 위주로 다루며, 증명이나 기타 자세한 내용에 대해서는 다루지 않으므로 다른 글을 참고하시길 부탁드립니다. Run Enumerate란? Run Enumerate는 문자열 내부에 연속하여 존재하는 모든 반복 또는 반복의 일부를 찾고 싶을 때 쓰는 알고리즘입니다. 예를 들어, $\rm{mississippi}$라는 문자열을 생각해봅시다. 이 문자열에는 어떤 반복이 존재할까요? 한번 나열해 봅시다. $[2, 4)$ 구간과 $[5,7)$ 구간에 해당하는 부분 문자열은 $\rm{ss}$로, 길이...
-
Suffix Automaton으로 Suffix Array 문제들을 풀어보자 2
이 포스트에서는 이전 글인 Suffix Automaton으로 Suffix Array 문제들을 풀어보자 1에 이어서, Suffix Automaton과 함께 사용할 수 있는 여러 테크닉들에 대해 설명합니다. Suffix Automaton이 무엇인지에 대해서는 제 이전 글을 참고하셔도 좋고, 아래 글을 읽어보셔도 좋습니다. https://koosaga.com/314 https://cp-algorithms.com/string/suffix-automaton.html DAG + Small to Large Suffix Automaton의 DAG에서 DP를 진행할 수도 있지만, 관리해야 하는 것이 어떤 값이 아닌 목록인 경우 Small to Large 테크닉을 활용할 수 있습니다. DAG에서 Small to Large를 활용하게 되는 대표적인 경우는, $n$개의 문자열 $S_1,...
-
Suffix Automaton으로 Suffix Array 문제들을 풀어보자 1
최근 공부 중에 Suffix Automaton이라는 자료 구조를 새로 알게 되어, Suffix Array 태그가 붙은 문제들을 전부 Suffix Automaton으로 풀어보려 시도했습니다. 그리고 꽤 많은 문제들이 Suffix Automaton을 사용할 때 훨씬 편리하게 풀린다는 것을 발견했습니다. 그 과정에서 알게 된 여러 테크닉들을 정리하고자 합니다. 이 글에서는 Suffix Automaton 자체에 대한 상세한 설명보다는 문제 풀이에 필요한 개념 위주로 간략하게 설명합니다. 아래에 Suffix Automaton에 대해 자세히 설명된 글이 있으니, 참고하시면 좋을 것 같습니다. https://koosaga.com/314 https://cp-algorithms.com/string/suffix-automaton.html Suffix Automaton이란? Suffix Automaton을 간단히...
-
문자열 해싱
이번 글에선 해싱의 다양한 활용을 정리하고자 한다. 너무 기본적인 내용이나 필자도 모르는 너무 고급 기술은 다루지 않고, solved.ac 기준 다이아 중하위 수준까지의 문제를 해싱을 이용해 풀어보려는 사람들에게 적합하다. 해시값을 관리하는 몇가지 방법들을 소개하고, 마지막으로는 며칠 전에 출제된 따끈따끈한 문제인 ICPC 2023 Seoul Regional에 출제된 E번 문항을 해싱을 써서 해결하는 방법을 소개하며 글을 마무리한다. 해싱이란? 문자열 x[0] ~ x[l-1] 이 주어져있을 때, 소수 $p, M$을 사용하여 계산한 해시값 $(\sum_{i=0}^{l-1} x_ip^i) \text{ mod M}$ 을 비교하여 다른...
-
Piece Table
서론 텍스트 에디터는 하나의 문자열을 조작하는 것을 매우 빠르게 하는 자료구조가 필요합니다. 길이가 $n$인 문자열 $s$에 대해서 다음과 같은 기능들이 있어야 합니다: $s = s[0..i] + s[j..n], 0 \le i < j \le n$, 즉, $i$ ~ $j$까지의 문자들을 지운다 $s = s[0..i] + t + s[i..n]$, 즉, $i$ 위치에 문자열 t를 넣는다 $s[i..j]$, 즉, $i$부터 $j$까지의 문자열을 빠르게 구한다 텍스트 에디터에는 문자열 찾기, 줄 번호 등 여러 기능이 있어야 하지만 우선 가장 중요한 기능은...
-
Python 3의 String 라이브러리 둘러보기
개요 이전에 Python 3에서 문자열 내의 부분 문자열을 빠르게 찾기 위한 fastsearch 기법에 대한 글을 쓴 적이 있습니다. 그 글에서는 문자열 중에서도 특정 기능에 대한 심도 있는 분석을 해보았었는데, Python의 철학이 담긴 대단히 세밀한 디자인과 구현체를 볼 수 있었습니다. 하지만 그것만으로는 Python의 str이 가진 수많은 특징 중 극히 일부 단면만을 보인 듯한 느낌이 들었습니다. 그래서, 이번에는 좀더 str의 전체적인 모습을 두루 살펴볼 수 있도록 보다 큰 그림을 통해 Python 3의 str의 구조는 어떻게 되며, string...
-
와일드카드 문자열 매칭
서론 문자열 매칭 알고리즘은, 문자열 $S$와 $T$가 주어졌을 때, $S$의 부분문자열(substring) 중에 $T$가 어느 위치에 등장하는지 찾는데 사용하는 알고리즘이다. 우리는 이 문자열 매칭 알고리즘에 와일드카드 문자, 즉, 어떤 문자에도 대응 될 수 있는 ? 문자가 들어갔을 때 어떤 식으로 문제를 해결해야 하는지 알아본다. ? 문자가 들어가지 않았을 때 문자열 매칭을 하는 법에 대해서는, KMP 알고리즘과 Aho-Corasick 알고리즘 문서에 잘 설명이 되어 있으니, 참고하면 된다. 문제 우리가 풀고 싶은 문제는 다음과 같다. 문자열 길이 $N$의 문자열...
-
접미사 트리 (파트 2: Ukkonen의 알고리즘)
이전 글에서 이어집니다. Ukkonen의 $O(m^3)$ 알고리즘 Ukkonen의 알고리즘은 접미사 트리를 $O(m)$에 만드는 알고리즘입니다. 하지만 이를 모두 설명하기에는 너무 복잡하니, 비효율적인 버전을 먼저 서술하고 시간 복잡도를 점차 줄여 나갑시다. (구현할 때도 파트 1을 먼저 구현하고, stress test 등으로 구현이 정확함을 확인하시는 것을 권합니다.) $S[1..i]$의 접미사 트리를 $I_i$라고 표기합시다. Ukkonen의 알고리즘의 큰 그림은 $I_1$에서 시작해서 이것을 $I_2$로 확장하고, $I_3$, $\cdots$, 마지막으로 $I_m$으로 확장하는 것입니다. $m$번째 글자가 끝 문자라고 가정하면 $I_m$의 모든 리프 노드와 접미사가 일대일 대응이 되지만,...
-
접미사 트리 (파트 1: 정의와 응용)
이 글은 트라이(trie) 자료구조에 대한 배경지식을 전제로 합니다. 부분문자열에 대한 다양한 문제를 선형 시간에 해결할 수 있는 접미사 트리 자료구조를 소개합니다. 이론 및 구현은 쉽지 않지만, 여러 문자열 문제들을 자명하게 만들거나 더 어려운 문자열 문제들을 해결하는 데 유용하게 쓸 수 있습니다. 문자열 $S$의 길이를 $m$이라고 하고, $i$번째부터 $j$번째까지 글자로 이루어진 부분문자열을 $S[i..j]$로 표기하겠습니다. 접미사 트라이 먼저, $S$의 모든 접미사로 이루어진 트라이를 생각해 봅시다. 이를 접미사 트라이(suffix trie)라고 합니다. 예를 들어 아래는 문자열 banana에 대한 접미사...
-
압축 트라이 (Compressed Trie)
서론 본 글에서는 트라이를 압축하여 트라이의 깊이를 $O(\sqrt (\sum \vert S \vert))$로 만드는 기법에 대해 설명하고자 합니다. 해당 방법은 트라이와 라빈-카프 알고리즘에 대한 선행 개념이 필요합니다. 해당 개념을 모르는 사람들을 위해 아래에 간략하게 설명하겠습니다. 트라이는 접두사 트리로, 어떤 문자열 집합의 prefix를 관리하는 자료구조입니다. 예를 들어 문자열 집합이 {“baby”, “bank”, “be”, “bed”, “box”, “dad”, “dance”}라면 이 집합을 표현한 트라이는 아래 그림과 같습니다. 이 때 붉은색 테두리는 여기서 끝나는 문자열이 존재한다는 것을 의미합니다. 이를 앞으로 valid한 노드라고...
-
KMP 알고리즘과 Aho-Corasick 알고리즘
본 글에서는 대표적인 문자열 검색 알고리즘인 KMP 알고리즘과 Aho-Corasick 알고리즘에 대해 다루려 한다. 두 알고리즘이 알고리즘계에서 잘 알려진 이유는 둘 모두 평균 시간 복잡도뿐 아니라 최악의 경우 시간 복잡도가 극적으로 개선되었기 때문이다. 두 알고리즘 모두 실제로는 다이나믹 프로그래밍의 한 예시일 뿐임에도 실제로는 어려운 알고리즘으로 생각되고 있었다. (내가 그랬다..) 풀고 싶은 문제 우리가 두 알고리즘을 이용해 풀고 싶은 문제는 아래와 같다. 1) 아주 긴 문자열 $S$ 와 짧은 문자열 $T$ 가 주어진다. $S$ 의 길이는 $N$,...
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 3)
동적 계획법을 최적화하는 9가지 방법 (Chapter 3) 이 글은 Chapter 2에서 계속된다. 8. Circular LCS 두 문자열 $S, T$ 가 주어질 때 둘의 LCS를 구하는 문제는 잘 알려져 있고, $n = S, m = T$ 일 때 $O(nm)$ 보다 빨리 하기 힘든 것으로도 유명하다. Circular LCS 문제는 $S$ 를 Cyclic shift 할 수 있을 때, 각 cyclic shift에 대해서 LCS를 계산하는 문제이다. 기호로 표현하면, 모든 $0 \le i \le S - 1$ 에 대해, $LCS(S[i:]...
-
Suffix Automaton 구현과 그 응용
목차 1. 개요 2. 구현 3. 응용 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 이번 포스트에서 살짝 양심고백을 한다면, 원리를 100% 이해하지 못하고 그 구현과 구현체만을 응용하는 것을 다루는 것을 리뷰하려고 합니다. Suffix Automaton의 구현과 동작이 모두 $O(N)$에 이루어지기 때문에 그 효율성 때문에 사용만 가능하다면 매우 유용할 것 입니다. Suffix Automaton의 원리를 전부 이해하고 구현한다면 참 좋겠지만, 아직 몇가지 소정리에 대해서 더 공부해야 이해가 제대로 될 것 같아서 구현방법만 집중적으로 설명하고, 응용에...
-
Palindromic Tree
목차 1. 개요 2. 개념 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 두달 전에 Manacher’s Algorithm 에 대해 소개했다. 이번에는 그것의 연장선상이며, 조금 지엽적이면서도 활용도가 높은 Palindromic Tree에 대해서 소개하고자 이 포스트를 쓰게 되었다. 이 포스트를 이해 하기 위해서는 간단한 오토마타에 대한 지식을 요구한다. 또한 KMP Algorithm에 대해 알고 있으면 이해하기 훨씬 수월하다. 또한 Manacher’s Algorithm 에 대한 지식이 없다면 Manacher’s Algorithm 에 대한 포스트를 한번 읽어보길 바란다. 또한 Trie에...
-
효율적인 긴 문자열 연산을 위한 Rope 자료구조
로프와 쿼리 최근 백준 온라인 저지에 로프와 쿼리라는 이름의 베타 문제가 올라왔습니다. 그런데 문제 본문의 어디를 보아도 로프라는 단어는 쓰이지 않고, 줄과 관련되어 보이는 부분도 없습니다. 그저 문자열의 일부를 잘라서 앞이나 뒤로 옮기는 쿼리를 수행하는 문제일 뿐입니다. 그러면 이 문제의 이름은 왜 로프와 쿼리인 걸까요? 일반적인 문자열 자료구조로는? 우선 이 문제를 단순한 std::string 객체로 해결을 시도해 봅시다. #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int q; cin...