ctrl+f를 누를 때마다 발생하는 문제를 살펴봅시다:
큰 텍스트 $t$가 있습니다. 그 안에서 문자열 $s$가 나타나는 위치를 모두 찾아야 합니다.
$t$의 길이 $|s|$인 모든 부분 문자열을 문자열 $s$와 비교하는 단순한 풀이는 $O(|t| \cdot |s|)$에 동작합니다. 텍스트가 크면 그 안에서 긴 단어를 찾는 데 매우 오랜 시간이 걸립니다.
그러나 이 문제를 $O(|s| + |t|)$에 해결하는 방법은 많으며, 그중 가장 널리 쓰이고 간단한 두 가지는 접두사 함수를 이용하는 방법과 Z 함수를 이용하는 방법입니다(참고: ‘지’가 아니라 ‘제트’라고 읽습니다).