34. KMP 문자열 매칭 알고리즘

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가 돌아가는 방식에 대한 이해의 깊이가 낮다.

 지금은 이대로 마무리하고 나중에 조금 더 이해가 깊어지면 이 문제들을 다시 짚어본다.