String2 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. KMP KMP Algorithm Knuth-Morris-Pratt Algorithm 문자열 S와 T가 주어질 때 S가 T를 포함하는지 판단하는 문자열 검색 알고리즘 1. 문자열 T에 대한 pi 배열(size=M)을 구한다. pi배열은 문자열 T 내의 반복된 문자열을 찾아 탐색 시간을 줄이는 데에 쓰인다. pi[ i ] = k ⇔ T[ 0 ~ k ] = T[ i-k ~ k ] ⇔ T의 부분문자열(0~i)의 앞/뒤에서부터 길이 k인 부분문자열이 서로 같다. // Get pi int M = T.size(); vector pi(M, 0); for (int i = 1, j = 0; i 0 && T[i] != T[j]) j = pi[j - 1]; if (T[i] == T[j]) p.. 2021. 4. 9. 이전 1 다음
