Algorithm7 Failure Function 길이 N 짜리 문자열에서 길이 M의 문자열을 검색하는 작업을 O(N+M)에 하는 KMP 알고리즘을 이해하려면, 우선 Failure Function (실패 함수) 를 이해해야 한다. 이 글에서는 Failure Function 에 관한 내용만 작성한다. 길이가 Len 인 문자열 S가 존재한다고 하자. 이 때 S의 index는 1-based 이다. 즉 S[1] ~ S[Len] 까지 문자가 있다. (개인적으로 이 알고리즘은 1-based가 더 직관적으로 이해하기 좋다고 생각한다.) Failure Function의 정의 1 ~ Len 범위의 수 i 에 대해 F(i) 를 아래와 같이 정의한다. F(i) := S[1...i] 에서 앞쪽 K자리의 문자열과 뒤쪽 K자리의 문자열이 일치하는 가장 큰 K (자기 자신은 제외.. 2022. 8. 19. 이전 1 2 다음
