Z 알고리즘

Z 알고리즘은 Z array를 빠르게 구하는 알고리즘이다. O(n)에 Z array를 구할수 있다.

Z array는 S와 S[i:]의 최대공통접두사의 길이를 저장하는 배열이다.

https://blog.chodaeho.com/posts/2021/z-algorithm/에서는 기본 구현과 조금 더 깔끔하게 정리한 구현, 두가지 방법을 소개한다

하지만 https://cp-algorithms.com/string/z-function.html#implementation 의 코드가 가장 깔끔하다. 나도 이쪽 구현을 python으로 포팅해서 사용했다.

z[0]이 가져야 하는 값은 정해져있지 않아서 보통은 0으로 저장하는 경우가 많지만, 내 경우는 len(s)로 저장하게 만들었다.

문자열에서도 설명할테니 그쪽 참고

대체적으로는 KMP의 failure function으로 할수 있는 것들과 많이 겹친다. prefix 관련된 것들을 구할 때 사용된다.

문자열 매칭 문제를 O(n+m)에 풀 수도 있다. P#S 라는 문자열을 만들어 Z 배열을 구하고, Z배열에서 z[i]==len(P)인 i를 모두 찾으면 된다.

문자열과 쿼리 (문자열을 뒤집은 뒤에) Z array를 구하기만 하면 된다.