PS 문자열 알고리즘 - 3. Z 알고리즘

지난번에 다루었던 KMP 알고리즘에 이어서, 이번에는 Z 알고리즘에 대해 다뤄보고자 한다. 바로 본론으로 들어가보자.

 

Z 알고리즘은 문자열 $S$가 주어졌을 때, 문자열 $S$의 접미사와 문자열 $S$의 최대 공통 접두사의 길이를 빠르게 구하는 알고리즘이다. 예시를 들면 아래와 같다.

Z array에 담기는 값

 

위 표와 같이 $Z[i]$에 $i$번째 문자로 시작하는 접미사와 원본 문자열의 공통 접두사의 최대 길이를 저장하는 알고리즘이 Z 알고리즘이고, Z 알고리즘으로 구한 이 array를 보통 Z array라고 부른다. 이 역시 Naive하게 구현하면 문자열의 길이가 $N$일 때 $O(N^2)$이 소요된다. Z 알고리즘은 이때 불필요한 탐색을 최적화하여 시간복잡도를 $O(N)$으로 줄인다. 그 원리는 아래와 같다.

 

idx               l         r
                  |         |
A C A B A C B ... A C A B A C A B C...
|---------|       |---------|
                      |
                      i

 

원본 문자열을 탐색하면서 Z array를 만들다 보니 위와 같이 $Z[l] = 6$이 되었다고 하자. $Z[l] = 6$이 우리에게 주는 정보는 원본 문자열의 index $0$ ~ $5$에 위치한 문자와 $l$ ~ $l+5$에 위치한 문자가 같다는 것이다. $Z[i](=Z[l+2])$를 채우려고 할 때 우리는 이 정보를 활용하면 $Z[l+2]$를 채울 때 $Z[2]$를 이용할 수 있음을 알 수 있다.

 

따라서 위의 경우에는 $Z[l+2] = Z[2] = 1$로 쉽게 값을 구할 수 있다. 한편, $i$가 계속 증가해 l+4 위치에 도달했다고 하자.

 

idx               l         r
                  |         |
A C A B A C B ... A C A B A C A B C...
|---------|       |---------|
                          |
                          i

 

이때도 $Z[l]$에서 얻은 정보를 이용하면 $Z[l+4]$를 채울 때 도움을 받을 수 있는 것처럼 보인다. 다만 이때에는 $Z[l+4] = Z[4]$라고 속단하면 안 된다. $Z[l+4]$의 값은 A C A B까지 공통되므로 4이지만, $Z[4]$는 2이다. 어떻게 된 일일까?

 

이러한 일이 벌어진 이유는 $Z[l+4]$의 범위가 $r$을 초과했기 때문이다. 즉, 우리가 얻은 정보는 $S[l+4] = S[4], S[l+5] = S[5]$가 전부이고 $S[l+6] != S[6]$이므로 $Z[l+4]$를 채울 때에는 $Z[4]$를 참고하더라도 2 이상이라는 정보만 알 수 있고, 그 이상은 직접 비교해보아야 한다.

 

그렇다면, 효율적인 연산을 위해서는 $r$의 값이 최대한 뒤에 있는 것이 기존의 정보를 최대한으로 활용하는 방법이기 때문에, $r$의 값이 원래보다 커지는 $l$이 존재하는 경우 $l, r$을 갱신해야 한다. 따라서 Z[l+4]에서 정보를 처리하고 나면 아래 그림과 같은 갱신이 이루어져야 한다.

idx                       l     r
                          |     |
A C A B A C B ... A C A B A C A B C...
|-----|                   |-----|
                          |
                          i

 

 

따라서,

• 1. $r$의 값을 이용해서 $Z[i]$ 구하기 
• 2. $Z[i]$의 범위가 $r$을 초과할 경우 직접 비교하기
• 3. $r$의 범위가 더 뒤로 옮겨질 수 있다면 $r$ 갱신하기

위 3가지를 이용하면 $Z$ 알고리즘을 구현할 수 있다.

아래는 문자열 $S$를 입력받아서 Z array를 구하는 파이썬 함수이다. 이때 $Z[0]$는 접미사와 원본 문자열이 동일하므로 정의에 따라 문자열 $S$의 길이가 되는 것이 자연스럽다. 하지만 큰 의미는 없어 $Z[0] = n$을 바로 할당하고 $i$는 $1$부터 $N$까지 반복하게 된다.

def makez(s):
    n = len(s)
    z = [0]*n; 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]) # z[i-l]에서 정보 가져오기
        while i+z[i] < n and s[i+z[i]] == s[z[i]]: # IndexError 방지
            z[i] += 1
        if r < i+z[i]-1:
            l, r = i, i+z[i]-1 # l, r 갱신
    return z

 

다음으로는 시간복잡도를 분석해보고자 한다. 이 역시 while문이 있어 시간복잡도 분석이 직관적이지 않다. 하지만 z[i] += 1의 시행 횟수와 $r$의 변화량 사이 관계에 주목하면 $O(N)$이 됨을 알 수 있다.

 

먼저, z[i] = min(r-i+1, z[i-l])에서 z[i-l]의 값을 가져온 경우 $z[i-l]$ 이후의 영역도 이미 비교가 완료되어 있고 서로 다름이 보장되어 있는 상황이므로 z[i] += 1이 행해지지 않는다.

 

따라서, z[i] += 1이 행해지는 경우에는 $i > r$이거나 $z[i]$에 바로 $r-i+1$이 할당된 상황임을 알 수 있고 두 경우 모두 z[i] += 1을 시행하기 전 $i+z[i]-1 \ge r$이 성립한다. 따라서 z[i] += 1이 k번 이루어졌다면 $r$이 $i+z[i]-1$로 갱신되므로 기존의 $r$ 값보다 $k$ 이상 커진다는 것을 의미한다. 이때 $r$의 최댓값은 $N$을 넘지 못하여 z[i] += 1의 시행 횟수도 같이 제한되고, z[i] += 1의 시행 횟수는 $i$가 $1$에서 $N$까지 도달할 때 통틀어 최대 $N$번이 된다. 따라서 위 알고리즘의 시간복잡도는 $O(N)$이 된다.

 

이제 이를 이용하는 문제를 풀어보자.

---

<BOJ 13713 문자열과 쿼리> https://www.acmicpc.net/problem/13713

Z 알고리즘에서 구하라는 것과 아주 살짝 다르게, 접두사와 원본 문자열의 최대 공통 접미사의 길이를 구하는 문제이다. 이 문제의 경우 주어진 문자열을 뒤집으면 Z 알고리즘의 상황과 동일하기 때문에 인덱스 처리에만 주의하면 쉽게 문제를 해결할 수 있다. 아래는 문제를 해결한 코드이다.

 

import sys
input = sys.stdin.readline
def makez(s):
    n = len(s)
    z = [0]*n; 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[i+z[i]] == s[z[i]]:
            z[i] += 1
        if r < i+z[i]-1:
            l, r = i, i+z[i]-1
    return z

s = input().rstrip()
z = makez(s[::-1])
m = int(input())
for _ in range(m):
    print(z[len(s)-int(input())])

 

---

<BOJ 16229 반복 패턴> https://www.acmicpc.net/problem/16229

이 문제는 앞선 문제보다는 조금 더 생각을 해야 하는 문제이지만, 역시나 어렵지 않다.

 

어떤 문자열의 반복으로 기존 문자열 길이인 $n$만큼은 최소한 채워야 하므로 길이 $i$짜리 문자열의 반복 패턴으로 만들고자 하면 $z[i]$ 자체가 문자열의 끝까지 도달해야 한다. 즉, $i+z[i] == n$을 만족해야 하고, $n$ 이상의 최소의 $i$의 배수 길이만큼으로 채울 때 길이가 $n+k$ 이하여야 한다는 조건까지 확인하면 충분하다.

단, $n$보다 $k$가 큰 경우에는 전체 문자열을 2번 이어붙인 문자열을 만들면 되므로 $n$을 바로 출력하면 된다.

 

아래는 문제를 해결한 내 코드이다.

import sys
input = sys.stdin.readline

def makez(s):
    n = len(s)
    z = [0]*n; 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[i+z[i]] == s[z[i]]:
            z[i] += 1
        if r < i+z[i]-1:
            l, r = i, i+z[i]-1
    return z

n, k = map(int, input().split())
s = input().rstrip()
z = makez(s)
if n <= k:
    print(n); exit(0)
ans = 0
for i in range(1, n):
    if i+z[i] == n and i*((n-1)//i+1) <= n+k:
        ans = i
print(ans)

 

---

 

Z 알고리즘에 해당하는 문제가 많지 않아 Z 알고리즘에 대한 글은 이 정도로 마친다. 다음에는 매내처 알고리즘에 대해 글을 써볼 예정이다.