Hash1 BOJ2020 부분 염기서열 2020번 부분 염기서열 주어진 염기서열을 문자열로 볼 때, 문자열의 모든 부분 문자열에 대해 m번 이상 나타나는 부분 문자열의 개수를 구하고 1)길이 2)사전식 으로 나열했을 때 k번째의 부분 문자열을 구한다. 두 가지 방법이 있다. 1. BFS 2. Suffix, Prefix 활용 두 방법 모두 길이 순으로 부분 문자열을 찾는다는 게 그나마의 공통점인 듯 1. BFS 길이가 len인 어떤 문자열 s가 m번 이상 등장한 경우 문자열 s를 prefix로 하고 길이가 len+1인 문자열 s'를 찾아 탐색하면서 길이가 짧은 순으로 문자열을 탐색할 수 있다. 아래 두 자료구조를 사용한다. queue Q; map M; 먼저 길이가 1인 부분 문자열을 찾아야 한다. for (int i = 0; i < n; i++.. 2021. 8. 25. 이전 1 다음