KMP2 KMP DP 트리 그래프 기하학 최근 푼 문제 1701 Cubeditor KMP idx(0~N-1)부터 N까지의 부분문자열에 대해 Pi를 구한다. idx에 대하여 최대 Pi값 - idx = 두 번 이상 나오는 가장 긴 부분문자열의 길이 * Pi를 구하는 시작점의 인덱스가 0이 아님에 주의해서 풀면 됨 16900 이름 정하기 KMP 주어진 문자열 S가 최소 K번 부분문자열로 등장하는 새로운 문자열 길이의 최솟값을 구한다. Pi를 구해 문자열 S에서 K-1번 반복해줄 부분 문자열을 구한다. 아래는 예시 S ada 3 pi 001 => (3-2)+2*3 S abc 2 pi 000 => (3-3)+3*2 S rr 5 pi 01 => (2-1)+1*5 S abcabcabca 3 pi 0001231234 => (10-3)+3*3 1509 팰린드롬 분할 DP 주.. 2021. 4. 16. 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 다음
