KMP 쉽게 이해하기 (Failure Function 이해)

여기서는 KMP 자체보다는 핵심인 Failure function 에 대한 설명만 한다. F 함수를 재귀로 디게 어렵게 설명한다음 뭐 어려운 것이다 원래 한번에 이해가 안되는게 당연하다고 하는데 혼자 해 보니까 사실 어려운 개념이 아니었다. F(i) 함수의 정의 : 문자열에서 1 ~ i 까지 항목을 고려했을 때, 접두사와 접미사가 같은 최대의 길이. 즉, ABABA 를 생각해 보자. F(1) 은 1 항목 (A) 를 고려해 보면 접두사와 접미사가 같은 최대 길이가 0 이다. F(2) 는 2 항목 (AB) 까지 고려해 보면 A랑 B가 다르니까 0 이다. F(3) 는 3 항목...

Read More