====== Z 알고리즘 ======
  * Z 알고리즘은 Z array를 빠르게 구하는 알고리즘이다. O(n)에 Z array를 구할수 있다.
  * 참고 :
    * [[https://cp-algorithms.com/string/z-function.html]]
    * [[https://blog.chodaeho.com/posts/2021/z-algorithm/]]

===== 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의 활용 =====
  * [[ps:문자열]]에서도 설명할테니 그쪽 참고
  * 대체적으로는 KMP의 failure function으로 할수 있는 것들과 많이 겹친다. prefix 관련된 것들을 구할 때 사용된다.
  * [[ps:문자열 매칭]] 문제를 O(n+m)에 풀 수도 있다. P#S 라는 문자열을 만들어 Z 배열을 구하고, Z배열에서 z[i]==len(P)인 i를 모두 찾으면 된다.

===== 관련 문제 =====
  * [[ps:problems:boj:13713]] (문자열을 뒤집은 뒤에) Z array를 구하기만 하면 된다.