패턴 검색을 위한 Z 함수

Z 함수는 패턴 검색에서 KMP를 대신할 수 있는 간결한 방법입니다. 많은 사람이 Z 함수를 더 쉽게 이해하고 구현합니다. ✨

각 인덱스에서 z[i]는 i에서 시작하여 전체 문자열의 접두사와 일치하는 가장 긴 부분 문자열의 길이입니다.

aabaab에서 z의 값은 0,1,0,3,1,0입니다. 인덱스 3에서는 aab 구간이 접두사와 일치하므로 길이가 3이 됩니다.

지금까지 찾은 가장 오른쪽의 일치 구간인 [l, r] 창을 추적합니다. 이를 이용하면 이전 비교 결과를 재사용할 수 있습니다.

i가 박스 안에 있을 때는 알려진 z 값을 복사하여 시작점으로 사용하고, 그 값이 박스의 오른쪽 경계를 넘지 않도록 제한합니다.

시작점 이후에는 접두사와 일치하는 동안 문자를 하나씩 계속 비교합니다.

일치 구간이 더 오른쪽까지 이어지면 l과 r을 갱신하여 이후 인덱스가 그 구간을 재사용할 수 있게 합니다.

박스는 오른쪽으로만 이동하므로 전체 작업량은 O(n)입니다. 각 문자가 기여하는 양에는 상한이 있습니다.

pattern + sep + text를 이어 붙인 뒤 Z를 실행합니다. 패턴 길이와 같은 z 값이 있으면 일치가 발생한 것입니다.

Z 배열을 훑으면서 z[i] == len(pattern)인 위치를 찾으면, 텍스트에서 해당 일치가 시작되는 위치를 알 수 있습니다.

Z와 KMP는 모두 선형 시간에 실행됩니다. Z는 코드를 작성하기 더 간단한 경우가 많으므로, 훌륭한 대체 도구가 됩니다.

Z 배열의 의미를 확실히 이해했는지 확인하세요.

이제 이동하는 박스를 이용해 Z 배열을 만들고, 선형 시간에 검색하며, KMP를 대신할 간결한 방법을 갖추었습니다. 🎯