z-function

z-function은 string에서 패턴매칭에 쓰이는 알고리즘이다

string s가 주어졌을 때 z[i]는 s[i:]와 s의 prefix의 longest substring의 길이를 나타낸다

 

s = abacaba 가 주어졌다고 하자

z[0] = 0 (s[0:]과 s는 동일한 string이기 때문에 원래 7이지만 0으로 하겠습니다)

z[1] = 0 (bacaba와 abacaba는 동일한 prefix가 없음)

z[2] = 1 (prefix 'a'가 동일함)

z[3] = 0 

z[4] = 3 (prefix 'aba'가 동일함)

z[5] = 0

z[6] = 1 (prefix 'a'가 동일함)

 

naive하게 구하면 O(n^2)이지만 z-function을 쓰면 O(n)이다

 

def compute_z_function(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(r - i + 1, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z

 

l과 r의 의미는 z[l:r+1]과 z[:r+l-1]이 동일하다는 의미입니다

l과 r을 이용하여 z[i]를 빨리 찾습니다

naive한 알고리즘은 z[i]를 구한후 z[i+1]을 구할때 s[i+1]부터 문자를 차례대로 비교를 합니다. 이 방식은 동일한 비교를 여러번 반복하게 되어 시간복잡도가 높습니다

 

z-function은 이러한 비효율성을 제거하기 위해 z[i]를 구한후 z[i+1]을 구할 때 s[i+1]부터 문자를 비교하는 것이 아닌 s[r+1]부터 문자를 비교하게 되어 반복 비교를 안하게 합니다

아래 그림에서 z[i]를 구하려고 할때 s[0:5]와 s[l:r+1]이 같기 때문에 z[2]를 사용할 수 있습니다

s[i]부터 s[r]까지만 prefix가 같기때문에 3(=r-i+1)보다 큰 값들에 대해서는 검증이 되지 않은 영역입니다

따라서 z[i]값을 3까지로 제한합니다. 이후 s[r+1] 값을 차례대로 비교하여 s[i]를 업데이트합니다

 

l,r 예시 설명

 

 

 

https://leetcode.com/problems/count-beautiful-splits-in-an-array/description/