Processing math: 100%

본문 바로가기

Z

(1)

91. Z Algorithm Z 알고리즘(Z Algorithm)은 문자열의 각각의 접미사와 전체 문자열의 가장 긴 공통 접두사의 길이를 빠르게 구하는 알고리즘이다. 이것도 설명이 간단하지는 않은데, 다음과 같은 예시를 보면 이해하기 쉽다. 문자열

$s = \ ^\shortparallel \mathsf{ababcacababa}^\shortparallel$ 이고

$|s| = n$ 이라고 하자.

$k$

$s_k$ 로 시작하는 접미사 접미사와 전체 문자열의 가장 긴 공통 접두사

$z(k)$

$0$

$\mathsf{ababcacababa}$

$\mathsf{ababcacababa}$

$12$

$1$

$\mathsf{babcacababa}$ (없음)

$0$

$2$

$\mathsf{abcacababa}$

$\mathsf{ab}$

$2$

티스토리툴바