알고리즘, 자료구조 중 '문자열매칭' ppt 개념설명 수업시연

목차

Section.01 원시적인 매칭 방법

Section.02 오토마타를 이용한 매칭

Section.03 라빈-카프 알고리즘 Rabin-Karp

Section.04 KMP 알고리즘

Section.05 보이어-무어 알고리즘

불일치 문자 휴리스틱과 일치 접미부 휴리스틱

본문내용

①while루프가 시간을 지배.
②에서 증가하거나
③에서 감소.
-> 변수 i와 j를 조합합 i+(i-j)를 도입.
while루프 돌 때마다 최소한 1 증가.
->②는 i와 j가 동시에 1증가.
따라서 i+(i-j)값 1 증가
->③은 j값만 감소.
i+(i-j)값은 1 이상 증가.
->매치 발생시 ④가 수행. ③과 같음.
따라서, 매 while루프마다 i+(i-j)값은 최소한 1이상 증가.
그러므로
i+(i-j) <= 2i
그런데 i<=n이어야 while 루프에 진입 가능
i+(i-j)<=2i<=2n
처음 while루프 진입시에 1로 시작해 2n을 넘을 수 없다. 매 while루프에서 하는 일은 상수 시간 작업. 따라서 while루프에 관련된 총 수행시간은 Θ(n)이다. 전처리과정은 Θ(m).
따라서 총 수행시간은 Θ(n)이다.

키워드

문자열 매칭,   알고리즘,   자료구조,   휴리스틱,   오토마타,   라빈카프,   kmp,   보이어 무어