길이가 $n$인 문자열 $s$의 Z 배열 $z[i]$는 $s[i]$에서 시작하는 부분 문자열이면서 $s$의 prefix이기도 한 가장 긴 문자열의 길이를 담는 배열이다. Z 배열을 통해서 패턴 매칭 문제 등을 해결할 수 있다.

Z 알고리즘을 사용해 Z 배열을 $O(n)$시간에 구하는 방법을 알아보자.