1. 개요
KMP 알고리즘은 간단한데 뭔가 생각의 한 벽을 깨야하는 듯한 느낌임.
시간은 Brute Force 방법보다 훨씬 진화한 O(N+M).
한 번 검사를 한 부분은 다시 반복하지 않기 위해서 prefix_table이라는 패턴 길이의 전역 배열이 필요함.
2. 문제
문자열 bacbabababacaca와 문자열 패턴 ababaca이 매칭되는지 검사하는 알고리즘을 기술하시오.
그리고 전수 조사법과 KMP 알고리즘의 수행시간을 비교하시오.
3. 코드
3-1) Prefix_Table()
3-2) KMP()
3-3) 출력
4. 정리
출력을 보면 알고리즘은 맞게 동작하지만 수행시간은 이론과 다르게 나타난다.
전수 조사법은 O(N*M)이고, KMP 알고리즘은 O(N+M)이지만 거의 동등한 수행시간을 보이며
오히려 KMP 알고리즘이 조금 더 늦다. 게다가 KMP 알고리즘은 추가적인 메모리 공간도 필요
하기에 훨씬 더 안 좋다. 이론과 다른 이 결과는 저번 코드 비교에도 나타났는데, 왜 이런 현상이
나타났는지는 아직 모르겠다. 무엇보다 현재 KMP가 돌아가는 방식에 대한 이해의 깊이가 낮다.
지금은 이대로 마무리하고 나중에 조금 더 이해가 깊어지면 이 문제들을 다시 짚어본다.
'Computer Science > 알고리즘' 카테고리의 다른 글
36. 매크로 함수의 위험2 - 성능 저하 (0) | 2016.09.06 |
---|---|
35. 매크로 함수의 위험1 - 논리 오류 (0) | 2016.09.06 |
33. 문자열 매칭 알고리즘 - 전수조사법(Brute Force) (0) | 2016.08.03 |
32. Floyd's 알고리즘(DP 방식으로 최단 경로 찾기 알고리즘) (0) | 2016.07.20 |
31. Hash 기초 문제 (1) 문자열에서 중복 문자 제거 알고리즘 (2) | 2016.07.17 |