사용자 도구

사이트 도구


ps:z_알고리즘

Z 알고리즘

Z array

  • Z array는 S와 S[i:]의 최대공통접두사의 길이를 저장하는 배열이다.
  • 주어진 문자열에 대해서 만들어진 z array의 예를 들면,
    • “aaaaa” ⇒  [X, 4, 3, 2, 1] 
    • “aaabaab” ⇒  [X, 2, 1, 0, 2, 1, 0] 
    • “abacaba” ⇒ [X, 0, 1, 0, 3, 0, 1]
    • (z[0]의 값은 보통 정의되지 않는다)

Z algorithm

Z array의 활용

  • 문자열에서도 설명할테니 그쪽 참고
  • 대체적으로는 KMP의 failure function으로 할수 있는 것들과 많이 겹친다. prefix 관련된 것들을 구할 때 사용된다.
  • 문자열 매칭 문제를 O(n+m)에 풀 수도 있다. P#S 라는 문자열을 만들어 Z 배열을 구하고, Z배열에서 z[i]==len(P)인 i를 모두 찾으면 된다.

관련 문제

토론

댓글을 입력하세요:
A F O X S
 
ps/z_알고리즘.txt · 마지막으로 수정됨: 2022/12/27 02:03 저자 teferi