[데이터구조] 패턴매칭 실패함수 동치증명

소개글

수학적 논리로 치밀하고, 자세하게 완벽을 기해서 증명을 완성했습니다. 한번 살펴보시면 패턴매칭 알고리즘을 깊이있게 이해할 수 있고, 엄밀한 논증의 형식을 연습해 볼 수 있습니다.

목차

정의
증명(수학적귀납)
(1) f(n+1) ≥ g(n+1)
(2) g(n+1) ≥ f(n+1)
종합

본문내용

패턴매칭을 위한 실패함수를 정의해서 사용하면, 선형의 시간복잡도를 갖는 알고리즘을 만들어낸다.
일단 탐색을 후퇴하지 않으면서 진행할 수있게 하기위해 실패함수를 직관적으로 알기 쉽게 함수 f 와 같이 정의 할 수 있는 데, 실패함수를 패턴길이에 대한 선형의 시간 복잡도를 갖는 알고리즘을 만드는데 편리하도록, 함수 g 와 같이 재정의 할 수 있다. 이 글은 두 함수가 서로 동치임을 증명한 것이다. 이 내용은 'C로 쓴 자료구조론(이석호역)' 94페이지의 연습문제 10.의 풀이에 해당한다.

참고 자료

c로 쓴 자료구조론(이석호역)