본문 바로가기

아호 코라식

[BOJ_Platinum 2] 10256-돌연변이 [python]
PS/BOJ (Baekjoon Online Judge) 2022. 2. 3. [BOJ_Platinum 2] 10256-돌연변이 [python] 10256번: 돌연변이 (acmicpc.net) 10256번: 돌연변이 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA www.acmicpc.net 문제 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA가 특정 문자열을 부분 문자열로 가진다면 그 질병에 걸릴 가능성이 높다는 것이다. 이러한 특정 문자열을 마커(marker)라 한다. 하지만 때때로 DNA 구조를 그대로 확인하는 것..
아호 - 코라식 (Aho-Corasick) 알고리즘
알고리즘 공부 2022. 1. 31. 아호 - 코라식 (Aho-Corasick) 알고리즘 아호-코라식 알고리즘은 대표적인 문자열 알고리즘 중 하나로써, 매우 빠른 일대 다 패턴 매칭 알고리즘입니다. 이와 관련해 설명하기 전에, 아호 코라식이 어떻게 쓰이는지, 왜 필요한지 간단한 예제를 통해 한번 알아보겠습니다. 주어진 단어가 다음과 같을 때, 트리는 아래처럼 구현됩니다. Words = {"HE","SHE","HIS"} 우리는 KSHE라는 문자열에서, 다음의 트라이에 포함되는 문자가 무엇이 있는지를 알고 싶습니다. 먼저, 기존의 방식처럼, 그냥 트라이를 따라 이동하는 경우를 생각해봅시다. 자식을 따라 이동하다가, 더이상 이동이 불가능한 경우, 시작 위치로 이동한다고 해봅시다. 현재 노드 Root 1 ) K로는 시작 노드에서 이동할 수 없으니 패스합니다. 현재노드 : Root 2 ) 시작노드에서..
728x90

티스토리툴바