알고리즘/문자열
2020. 8. 11.
Z
길이가 \(n\)인 문자열 \(S\)가 있습니다. (0-index) 이 문자열의 각 인덱스 \(i\)에 대해서, \(S\)와 부분 문자열 \(S[i..n)\)의 공통 최대 접두사의 길이를 구하려고 합니다. 어떻게 하면 될까요? 나이브하게 구하면 \(O(n^2)\)에 해결할 수 있습니다. 이를 \(O(n)\)에 구하는 Z 알고리즘에 대해 알아봅시다. \(S[l...r)\)을 현재 \(S\)의 prefix와 일치하는 구간으로 정의합시다. \(S[l..r) = S[0..r-l)\)입니다. 초기에 \(l = r = 0\)입니다. 각 인덱스에 대해서 \(S\)와의 공통 최대 접두사의 길이를 구하면서 배열 \(Z\)에 저장합니다. 먼저 \(S[0..n) = S\)이므로, 첫 번째 인덱스에서 이를 구하는 것은 의미가..