어떤때 사용할까?
- z-algorithm이란 특정 문자열 s에 대해
s와
s[1:]
s[2:]
...
s[len(s) - 1:]- 까지의 모든 부분 문자열에 대해 s와 비교시 가장 긴 prefix를 각각 다 찾는 알고리즘이다.
브루트 포스로 접근시?
- 단순하게 생각하면 각각의 suffix에 대해 직접 문자열을 비교하면 된다.
def brute_force(s: str) -> list[int]:
N = len(s)
z_array = [0] * N
for i in range(N):
count = 0
while i + count < N and s[count] == s[i + count]:
count += 1
z_array[i] = count
return z_array- 예를 들어
s = "ababa"라고 해보자.
s = ababa
s[0:] = ababa -> ababa와 비교 -> 5
s[1:] = baba -> ababa와 비교 -> 0
s[2:] = aba -> ababa와 비교 -> 3
s[3:] = ba -> ababa와 비교 -> 0
s[4:] = a -> ababa와 비교 -> 1- 따라서 z-array는 다음과 같다.
[5, 0, 3, 0, 1]- 문제는 이 방식이 너무 느리다는 것이다.
- 최악의 경우를 생각해보자.
s = "aaaaaa"- 이 경우 모든 suffix가 prefix와 상당히 길게 겹친다.
s[0:] = aaaaaa -> 6번 비교
s[1:] = aaaaa -> 5번 비교
s[2:] = aaaa -> 4번 비교
s[3:] = aaa -> 3번 비교
s[4:] = aa -> 2번 비교
s[5:] = a -> 1번 비교- 즉 대략 다음과 같은 비교가 발생한다.
N + (N - 1) + (N - 2) + ... + 1- 따라서 시간복잡도는
O(N^2)이 된다. - 문자열 길이가 작으면 괜찮지만,
N = 10^5같은 입력에서는 사실상 불가능하다.
그래서 뭘 줄여야 할까?
- 브루트 포스가 느린 이유는 이미 비교한 정보를 버리기 때문이다.
- 예를 들어 어떤 구간에서 이미 prefix와 일치한다는 사실을 알고 있는데도,
- 다음 위치로 이동하면 다시 처음부터 비교한다.
prefix: a b a b a ...
suffix: a b a ...- 여기서 이미
aba가 같다는 사실을 알았다면, - 다음 비교에서도 이 정보를 어느 정도 재사용할 수 있어야 한다.
- z-algorithm의 핵심은 바로 이 부분이다.
이미 prefix와 일치한다고 확인한 구간을 기억해두고,
그 안에 들어오는 위치는 가능한 만큼 기존 값을 재사용한다.
Z-box
- z-algorithm에서는 현재까지 발견한 prefix 일치 구간을 하나 관리한다.
- 보통 이 구간을
[left, right]라고 둔다.
s = a b a b a ...
^ ^
left right- 이 의미는 다음과 같다.
s[left:right + 1]구간은
s[0:right - left + 1]와 동일하다.
- 즉
left에서 시작하는 어떤 부분 문자열이 prefix와 일치하고 있다는 뜻이다.
s[0 ...] = a b a
s[left ...] = a b a- 이 구간을 알고 있으면,
left와right사이에 있는 인덱스들은 처음부터 다시 비교할 필요가 없다.
현재 위치 i가 Z-box 밖에 있는 경우
- 만약 현재 위치
i가right보다 크다면, 현재 알고 있는 일치 구간 밖에 있는 것이다.
[left .... right] i- 이 경우에는 재사용할 정보가 없다.
- 그래서 그냥 브루트 포스처럼 직접 비교를 시작한다.
left = right = i
while right < N and s[right - left] == s[right]:
right += 1
right -= 1
z_array[i] = right - left + 1- 여기서
right - left는 prefix 쪽 인덱스다. - 예를 들어
left = i라면,
s[0] vs s[i]
s[1] vs s[i + 1]
s[2] vs s[i + 2]
...- 이런 식으로 비교하는 것이다.
현재 위치 i가 Z-box 안에 있는 경우
- 더 중요한 부분은
i <= right인 경우다.
left i right
|----------|---------|- 이 경우
i는 이미 prefix와 일치한다고 검증된 구간 안에 있다. - 따라서
i에 대응되는 prefix 쪽 위치를 찾을 수 있다.
k = i - left- 왜냐하면
[left, right]구간은 prefix와 동일하기 때문이다.
s[0] == s[left]
s[1] == s[left + 1]
s[2] == s[left + 2]
...
s[k] == s[i]- 그래서
z_array[k]값을 참고할 수 있다. - 즉, prefix 내부에서 이미 계산해둔 값을 현재 위치에도 어느 정도 가져다 쓸 수 있다.
z_array[k]와 remaining 비교
- 여기서 중요한 값이 하나 더 있다.
remaining = right - i + 1- 이 값은 현재
i부터 Z-box 끝까지 남아있는 길이다.
left i right
|----------|---------|
<--------->
remaining- 이제
z_array[k]와remaining을 비교한다.
1. z_array[k] < remaining
if z_array[k] < remaining:
z_array[i] = z_array[k]- 이 경우는
z_array[k]가 Z-box 내부에서 완전히 끝난다는 뜻이다.
prefix 쪽에서 이미 불일치가 확인된 위치가
현재 Z-box 내부에도 그대로 대응된다.- 따라서 더 비교할 필요가 없다.
- 그냥
z_array[k]를 그대로 가져오면 된다.
z_array[i] = z_array[k]- 이게 가능한 이유는 현재 구간이 prefix와 동일하다고 이미 알고 있기 때문이다.
2. z_array[k] >= remaining
else:
left = i
while right + 1 < N and s[right - left + 1] == s[right + 1]:
right += 1
z_array[i] = right - left + 1- 이 경우는 다르다.
z_array[k]가 현재 Z-box 끝까지 닿거나, 그 밖으로 튀어나갈 가능성이 있다는 뜻이다.
left i right
|----------|---------|
<--------->
remaining
z_array[k]가 remaining 이상- Z-box 내부에서는 이미 같다는 것이 보장된다.
- 하지만
right이후는 아직 비교해본 적이 없다. - 따라서
right + 1부터 추가 비교를 해야 한다.
이미 아는 부분: i ~ right
새로 확인할 부분: right + 1부터- 그래서 이때는
left = i로 갱신하고, - Z-box를 오른쪽으로 확장할 수 있는 만큼 확장한다.
z_array를 구하는 함수
def z_algorithm(s: str) -> list[int]:
N = len(s)
z_array = [0] * N
z_array[0] = N
left = right = 0
for i in range(1, N):
if i > right:
"""
Outside of the Z-box
"""
left = right = i
while right < N and s[right - left] == s[right]:
right += 1
right -= 1
z_array[i] = right - left + 1
else:
"""
Inside of the Z-box
"""
k = i - left
remaining = right - i + 1
if z_array[k] < remaining:
z_array[i] = z_array[k]
else:
left = i
while right + 1 < N and s[right - left + 1] == s[right + 1]:
right += 1
z_array[i] = right - left + 1
return z_array시간복잡도
- 얼핏 보면 while문이 중첩되어 있어서
O(N^2)처럼 보일 수 있다. - 하지만 실제로는 그렇지 않다.
- 핵심은
right가 한 번 증가하면 다시 왼쪽으로 돌아가지 않는다는 것이다.
right는 전체 알고리즘 동안 최대 N번만 증가한다.- 따라서 전체 비교 횟수는 선형에 가깝게 제한된다.
- 결과적으로 z-algorithm의 시간복잡도는 다음과 같다.
O(N)- 공간복잡도는 z-array를 저장하므로 다음과 같다.
O(N)정리
- z-algorithm은 모든 suffix에 대해 원본 문자열과의 longest common prefix 길이를 구하는 알고리즘이다.
- 브루트 포스로 하면 각 suffix마다 처음부터 비교하므로 최악의 경우
O(N^2)이 된다. - z-algorithm은 이미 prefix와 일치한다고 확인한 구간인 Z-box
[left, right]를 관리한다. - 현재 위치가 Z-box 안에 있으면, prefix 쪽에서 이미 계산한 값을 재사용한다.
- 단, Z-box 밖으로 튀어나갈 가능성이 있는 경우에만 추가 비교를 한다.
- 그래서 전체 시간복잡도를
O(N)으로 줄일 수 있다.
패턴 매칭에 사용하기
- z-algorithm은 특정 문자열과 그 suffix들의 longest common prefix를 빠르게 구하는 알고리즘이다.
- 그런데 이걸 조금 응용하면 패턴 매칭에도 사용할 수 있다.
- 즉, 어떤 문자열
text안에서pattern이 등장하는 위치를 찾을 수 있다.
예를 들어 다음과 같은 상황을 생각해보자.
pattern = "aba"
text = "abacaba"- 여기서 우리가 알고 싶은 것은 다음과 같다.
text 안에서 pattern이 시작되는 위치는 어디인가?- 직접 보면
aba는 다음 위치에 등장한다.
text = a b a c a b a
0 1 2 3 4 5 6
pattern = aba
등장 위치: 0, 4문자열을 합쳐서 생각하기
-
z-algorithm은 항상 어떤 문자열의 prefix와 suffix를 비교한다.
-
그러면 패턴 매칭을 하려면 어떻게 해야 할까?
-
간단하다.
-
pattern을 앞에 두고, 그 뒤에text를 붙이면 된다.
combined = pattern + "#" + text- 여기서
#는 구분자다. - 즉 다음과 같은 문자열을 만든다.
pattern = aba
text = abacaba
combined = aba#abacaba- 왜 굳이
#같은 구분자를 넣을까? - 패턴과 텍스트가 서로 섞여서 이상하게 매칭되는 것을 막기 위해서다.
aba#abacaba- 이제 이 문자열에 대해 z-array를 구한다.
- 그러면 각 위치마다 다음 값을 알 수 있다.
combined의 prefix와
combined[i:]가 얼마나 길게 일치하는가?
- 그런데 combined의 prefix는 곧
pattern이다.
combined prefix = aba- 따라서 어떤 위치의 z값이
len(pattern)이상이라면, - 그 위치부터 pattern 전체가 일치한다는 뜻이다.
예시로 보기
combined = aba#abacaba- 인덱스를 붙이면 다음과 같다.
index = 0 1 2 3 4 5 6 7 8 9 10
combined = a b a # a b a c a b a- 여기서
text가 시작되는 위치는len(pattern) + 1이다.
text_start = len(pattern) + 1- 현재 예시에서는 다음과 같다.
text_start = 3 + 1
text_start = 4- 즉 combined의 4번 인덱스부터 원래 text가 시작된다.
combined = a b a # a b a c a b a
index = 0 1 2 3 4 5 6 7 8 9 10
^
text 시작z-array 값 해석하기
- 이제 z-array를 구했다고 해보자.
combined = aba#abacaba
z_array = [11, 0, 1, 0, 3, 0, 1, 0, 3, 0, 1]- 여기서 중요한 값은
3이다. - 왜냐하면 pattern의 길이가 3이기 때문이다.
len(pattern) = 3- z값이 3 이상인 위치를 보면 다음과 같다.
index 4 -> z_array[4] = 3
index 8 -> z_array[8] = 3- 이 말은 combined의 4번 위치와 8번 위치에서 prefix인
"aba"가 완전히 일치한다는 뜻이다.
combined[4:] = abacaba
aba 일치
combined[8:] = aba
aba 일치-
그런데 우리가 원하는 것은 combined 기준 인덱스가 아니다.
-
원래 text 기준 인덱스가 필요하다.
-
combined에서 text는 4번 인덱스부터 시작했다.
-
따라서 다음처럼 빼주면 된다.
text_index = combined_index - text_start- 그러면 다음과 같이 변환된다.
combined index 4 -> text index 0
combined index 8 -> text index 4- 따라서 정답은 다음과 같다.
[0, 4]코드로 작성하기
- 먼저 기존에 작성한
z_algorithm함수를 그대로 사용한다.
def z_algorithm(s: str) -> list[int]:
N = len(s)
z_array = [0] * N
z_array[0] = N
left = right = 0
for i in range(1, N):
if i > right:
left = right = i
while right < N and s[right - left] == s[right]:
right += 1
right -= 1
z_array[i] = right - left + 1
else:
k = i - left
remaining = right - i + 1
if z_array[k] < remaining:
z_array[i] = z_array[k]
else:
left = i
while right + 1 < N and s[right - left + 1] == s[right + 1]:
right += 1
z_array[i] = right - left + 1
return z_array- 이제 패턴 매칭 함수를 만들 수 있다.
def find_pattern(text: str, pattern: str) -> list[int]:
combined = pattern + "#" + text
z_array = z_algorithm(combined)
pattern_length = len(pattern)
text_start = pattern_length + 1
result = []
for i in range(text_start, len(combined)):
if z_array[i] >= pattern_length:
result.append(i - text_start)
return result- 테스트해보면 다음과 같다.
text = "abacaba"
pattern = "aba"
print(find_pattern(text, pattern))[0, 4]왜 이게 되는 걸까?
- 핵심은 combined 문자열의 prefix가 pattern이라는 점이다.
combined = pattern + "#" + text- z-array는 각 위치에서 prefix와 얼마나 길게 일치하는지를 알려준다.
- 그런데 prefix 자체가 pattern이므로,
- 어떤 위치의 z값이 pattern 길이 이상이면 그 위치부터 pattern이 등장한 것이다.
z_array[i] >= len(pattern)- 이 조건은 다음 의미와 같다.
combined[i:i + len(pattern)] == pattern- 즉, z-algorithm을 사용하면 모든 위치에서 pattern과 일치하는지를 한 번에 검사할 수 있다.
브루트 포스와 비교
- 브루트 포스로 패턴 매칭을 하면 각 위치마다 pattern을 직접 비교해야 한다.
def brute_force_pattern_matching(text: str, pattern: str) -> list[int]:
result = []
for i in range(len(text) - len(pattern) + 1):
matched = True
for j in range(len(pattern)):
if text[i + j] != pattern[j]:
matched = False
break
if matched:
result.append(i)
return result- 이 방식은 최악의 경우 다음과 같은 시간복잡도를 가진다.
O(NM)-
여기서
N은 text의 길이, -
M은 pattern의 길이다. -
예를 들어 다음처럼 같은 문자가 반복되는 경우를 생각해보자.
text = "aaaaaaaaaa"
pattern = "aaaaa"-
각 위치마다 거의 pattern 전체를 비교해야 한다.
-
그래서 입력이 커지면 상당히 느려질 수 있다.
-
반면 z-algorithm을 사용하면 combined 문자열 하나에 대해 z-array를 한 번만 구하면 된다.
combined length = len(pattern) + 1 + len(text)- 따라서 시간복잡도는 다음과 같다.
O(N + M)전체 코드
def z_algorithm(s: str) -> list[int]:
N = len(s)
z_array = [0] * N
z_array[0] = N
left = right = 0
for i in range(1, N):
if i > right:
left = right = i
while right < N and s[right - left] == s[right]:
right += 1
right -= 1
z_array[i] = right - left + 1
else:
k = i - left
remaining = right - i + 1
if z_array[k] < remaining:
z_array[i] = z_array[k]
else:
left = i
while right + 1 < N and s[right - left + 1] == s[right + 1]:
right += 1
z_array[i] = right - left + 1
return z_array
def find_pattern(text: str, pattern: str) -> list[int]:
combined = pattern + "#" + text
z_array = z_algorithm(combined)
pattern_length = len(pattern)
text_start = pattern_length + 1
result = []
for i in range(text_start, len(combined)):
if z_array[i] >= pattern_length:
result.append(i - text_start)
return result
만능 컴덕후 겸 번지 팬