문자열과 접미사의 가장 긴 공통 접두사의 길이를 찾는 z 알고리즘 배우기

1. z - function 길이 n인 문자열 s에 대하여 z[i]는 s의 i번째 접미사 s[i,i+1,...]과 s와의 최대 공통 접두사의 길이를 말한다 정의에 의하면 z[0]는 s와 s의 최대 공통 접두사의 길이로 s 그 자체의 길이 n이 될텐데 일반적으로 잘 정의하지 않는다. z[0] = 0으로 정의하기도 하고 문제에 따라 필요하다면 z[0] = n으로 정의하기도 한다. 예를 들어 'abacaba'에 대하여... z[1]은 'abacaba'와 'bacaba'의 최대 공통 접두사의 길이로... 공통 접두사가 존재하지 않으니 0 z[2]는 'abacaba'와 'acaba'의 최대 공통 접두사의 길이로 'a'가 있으니 z[2] = 1 z[3]은 'abacaba'와 'caba'의 최대 공통 접두사의 길이로..