본문 바로가기

알고리즘/문자열

알고리즘/문자열 2021. 2. 17. Aho–Corasick 문자열 \(S\)에서 하나의 문자열을 검색하는 것은 간단합니다. 그런데 검색해야 할 문자열이 여러개라면 어떨까요? 일반적인 문자열 탐색 알고리즘으로는 이를 빠르게 처리할 수 없으므로, 다른 방법을 생각해 내야 합니다. 문자열 \(S\)가 있고, 크기가 \(n\)인 문자열의 집합 \(T\)가 있습니다. \(S\)에서 \(T\)에 속한 문자열 중 적어도 하나를 검색할 수 있는지 여부를 알고 싶습니다. \(T\)의 크기가 1이라면, 우리는 KMP알고리즘을 이용해 \(O(|S|+|T|)\)에 검색이 가능하다는 것을 알고 있습니다. anz1217.tistory.com/56 KMP 대부분의 문자열 알고리즘은 어떤 문자열이 주어졌을 때, 이 부분 문자열 중 조건에 만족하는 특정한 문자열을 찾는 알고리즘입니다. 가장 ..
알고리즘/문자열 2021. 2. 16. Suffix Array와 LCP배열 문자열 \(S\)가 주어졌을 때, 이 문자열의 모든 접미사(suffix)를 사전순으로 정렬해 봅시다. 가장 단순한 방법은 \(|S|\)개의 suffix를 만든다음, 직접 정렬하는 것입니다. 이 방법을 이용하면 \(O(n^2 \log n)\)의 시간복잡도로 Suffix Array를 만들 수 있습니다. (\(n = |S|\)) www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 물론 이는 문자열의 길이가 조금만 길어져도 쓸 수 없는 방법이므로, 다른 방법을 생각해 봅시다. 다음과 같은 문자열이 있습니다. (0-index) \(S = \) "ab..
알고리즘/문자열 2021. 2. 5. Manacher 길이가 \(n\)인 문자열 \(S\)가 있습니다. 이 문자열의 부분 문자열 중 팰린드롬인 것을 모두 알고 싶다면, 어떻게 하면 될까요? 나이브하게 \(O(n^3)\) 또는 \(O(n^2)\)로도 해결할 수 있겠지만, 이를 \(O(n)\)에 해결할 수 있는 Manacher 알고리즘에 대해 알아봅시다. \(S\)의 각 \(i\)번째 문자를 중심으로 하는 팰린드롬의 최대 반지름을 \(A_i\)라고 정의합시다. 또, \(j m\) 현재 얻을 수 있..
알고리즘/문자열 2020. 8. 11. Z 길이가 \(n\)인 문자열 \(S\)가 있습니다. (0-index) 이 문자열의 각 인덱스 \(i\)에 대해서, \(S\)와 부분 문자열 \(S[i..n)\)의 공통 최대 접두사의 길이를 구하려고 합니다. 어떻게 하면 될까요? 나이브하게 구하면 \(O(n^2)\)에 해결할 수 있습니다. 이를 \(O(n)\)에 구하는 Z 알고리즘에 대해 알아봅시다. \(S[l...r)\)을 현재 \(S\)의 prefix와 일치하는 구간으로 정의합시다. \(S[l..r) = S[0..r-l)\)입니다. 초기에 \(l = r = 0\)입니다. 각 인덱스에 대해서 \(S\)와의 공통 최대 접두사의 길이를 구하면서 배열 \(Z\)에 저장합니다. 먼저 \(S[0..n) = S\)이므로, 첫 번째 인덱스에서 이를 구하는 것은 의미가..
알고리즘/문자열 2020. 8. 5. 해싱 두 문자열이 같은 문자열인지 확인하려고 합니다. 물론 두 문자열의 길이만큼 직접 비교하는 식으로 확인할 수 있지만, 두 문자열의 해시값이 같은지 확인하는 방식으로도 확인할 수 있습니다. 해시 함수에는 다양한 종류가 있지만, 이 문제에 나오는 해시 함수를 이용합니다. https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정� www.acmicpc.net 라빈-카프 알고리즘(Rabin-Karp Algorithm) 어떤 문자열 \(S\)가 주어졌을 때, 이 문자열의 일정한 \(L\)길..
알고리즘/문자열 2020. 7. 23. 트라이 여러 문자열을 저장하는 자료구조인 트라이(Trie)에 대해 알아봅시다. 문자열 집합 { "ab", "abc", "acd", "bcd", "be"} 가 있다고 할 때, 트라이는 문자열을 다음과 같은 트리로 저장합니다. 문자열을 트라이에 저장하면 루트 노드에서부터 시작해서, 앞에서부터 한 글자씩 해당하는 자식노드를 따라가게 됩니다. 문자열을 모두 저장했다면, 현재 노드에 저장된 문자열이 있다는 표시를 해 주면 됩니다. (그림에서 짙은 노드) 시간복잡도는 문자열 삽입에 \(O(L)\), 탐색에 \(O(L)\)입니다. (\(L\) : 문자열의 길이) 문자열을 set등의 BST로 저장하는 것보다 삽입, 탐색이 훨씬 빠르고, 해싱으로 저장했을 때의 충돌이 없기 때문에 안정적으로 문자열을 찾고 저장할 수 있습니다. ..
알고리즘/문자열 2020. 7. 21. KMP 대부분의 문자열 알고리즘은 어떤 문자열이 주어졌을 때, 이 부분 문자열 중 조건에 만족하는 특정한 문자열을 찾는 알고리즘입니다. 가장 단순하게, 문자열 \(S\)에서 문자열 \(T\)를 찾는 방법에 대해 알아봅시다. 문자열을 검색하는 가장 단순한 방법은, 이중 포문을 돌려 \(O(|S||T|)\)의 시간복잡도로 검색하는 것입니다. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 하지만 \(S\)와 \(T\)의 길이가 각각 최대 100만..

티스토리툴바