위치마다 비교하는 접두사
문자열 s의 i번째 위치에서 오른쪽으로 읽은 내용과 s의 처음부터 읽은 내용을 비교한다. 처음 다른 문자가 나오거나 문자열 끝에 도달할 때까지 일치한 문자 수가 z[i]다. 중간 문자를 건너뛰어 찾는 부분수열의 길이가 아니라 연속한 일치 길이를 뜻한다.
짧은 예로 읽기
문자열이 abcabxabc라면 i=3에서는 ab가 처음의 ab와 일치하지만 다음 x와 c가 다르므로 z[3]=2다. i=6에서는 abc가 문자열 끝까지 일치하므로 z[6]=3이다. i=1의 b는 첫 문자 a와 다르므로 z[1]=0이다. z[0]은 구현 관례에 따라 0이나 전체 길이로 두므로 결과를 비교할 때 확인한다.
일치 구간의 재사용
각 위치에서 처음부터 비교하면 같은 문자를 반복해서 확인하여 최악 O(n²)이 걸린다. 선형 알고리즘은 접두사와 일치한다고 이미 확인한 구간의 오른쪽 끝을 관리한다. 현재 위치가 그 안에 있으면 앞서 계산한 값을 구간 안에서 재사용하고, 확인되지 않은 오른쪽 부분만 추가 비교한다.
패턴 검색에 활용
패턴과 구분자와 본문을 이어 붙인 문자열의 Z 값을 계산할 수 있다. 구분자는 두 문자열에 나타나지 않는 문자를 사용한다. 본문에 해당하는 위치에서 일치 길이가 패턴 길이 이상이면 패턴이 그곳에 나타난다. 문자 인덱스가 바이트인지 문자 단위인지도 구현에서 일관되어야 한다.