반응형 aho-corasick 썸네일형 리스트형 [BOJ 2809] 아스키 거리 [문제] www.acmicpc.net/problem/2809 2809번: 아스키 거리 첫째 줄에 거리의 길이 N이 주어진다. 다음 줄에는 거리에 원래 적혀져있는 알파벳이 주어진다. 셋째 줄에는 묶음 타일의 종류의 개수 M이 주어진다. 다음 M개 줄에는 각 묶음 타일에 적혀져있는 www.acmicpc.net [난이도] - Platinum 2 (20.12.11 solved.ac 기준) [필요 개념] - 아호코라식 (Aho-corasick) [풀이] 아호코라식 문자열 판별 알고리즘의 응용문제이다. 타일과 일치하는 부분을 제외한 문자의 개수를 구하는 문제인데, 단순하게 아스키 거리의 각 위치(index) 별로 끝에 일치하는 타일들을 모두 고려한다면 시간 초과가 발생할 것 같다....? (정확하게는 모르겠다) 따.. [BOJ 10256] 돌연변이 [문제] www.acmicpc.net/problem/10256 10256번: 돌연변이 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA www.acmicpc.net [난이도] - Platinum 3 (solved.ac 20.12.11 기준) [필요 개념] - 아호코라식 (Aho-corasick) [풀이] 마커(marker)의 돌연변이의 경우의 수는 최대 $m^2$이다. m이 100이하이므로 모든 돌연변이를 직접 다 만들어도 무리가 없다. 그리고, 만들어진 돌연변이들을 트라이에 넣어두고, DNA문자열을 탐색한다. 이때, 모든 돌연변이들의 길이가.. 이전 1 다음