ps:z_알고리즘
Z 알고리즘
- Z 알고리즘은 Z array를 빠르게 구하는 알고리즘이다. O(n)에 Z array를 구할수 있다.
- 참고 :
Z array
- Z array는 S와 S[i:]의 최대공통접두사의 길이를 저장하는 배열이다.
- 주어진 문자열에 대해서 만들어진 z array의 예를 들면,
- “aaaaa” ⇒ [X, 4, 3, 2, 1]
- “aaabaab” ⇒ [X, 2, 1, 0, 2, 1, 0]
- “abacaba” ⇒ [X, 0, 1, 0, 3, 0, 1]
- (z[0]의 값은 보통 정의되지 않는다)
Z algorithm
- https://blog.chodaeho.com/posts/2021/z-algorithm/에서는 기본 구현과 조금 더 깔끔하게 정리한 구현, 두가지 방법을 소개한다
- 하지만 https://cp-algorithms.com/string/z-function.html#implementation 의 코드가 가장 깔끔하다. 나도 이쪽 구현을 python으로 포팅해서 사용했다.
- z[0]이 가져야 하는 값은 정해져있지 않아서 보통은 0으로 저장하는 경우가 많지만, 내 경우는 len(s)로 저장하게 만들었다.
Z array의 활용
관련 문제
- 문자열과 쿼리 (문자열을 뒤집은 뒤에) Z array를 구하기만 하면 된다.
ps/z_알고리즘.txt · 마지막으로 수정됨: 2022/12/27 02:03 저자 teferi
토론