[알고리즘] Knuth-Morris-pratt Algorithm, KMP 알고리즘

■KMP 알고리즘

KMP알고리즘에 대해 간략히 설명 하자면, 지금까지 알려진 문자열 알고리즘 가운데 가장 최저의 시간복잡도를 가진 알고리즘이다. 

일단, KMP알고리즘의 시간복잡도는 O(N+K) 여기서 N과 K는 비교할 문자열의 길이이다. 매칭을 하려면 최소한 비교대상과 타겟의 문자열을 한번씩 읽어봐야 할테니, 가장 최적의 시간복잡도이다.

알고리즘에 대한 기본적인 설명과 이해는 아래의 링크를 통해서 천천히 반복적으로 학습하는 것을 추천하고, 본인 역시 아래의 링크를 참고해서 학습한 내용에 이해에 필요한 설명을 추가하려 포스팅하려고 한다.

>http://bywords.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-KMP-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

>http://blog.naver.com/slaltats/120024010626

● 실패함수

위의 링크에서 또는 여러방법으로 KMP알고리즘의 이론에 대해 학습을 했다면, 실패함수의 테이블 값들이 왜 저렇게 만들어지는가에 대한 궁금증은 없을 것이라고 생각된다. 추가적으로 슬라이드에 있는 내용을 통해 한번 더 체크해보자.

● 비교함수

비교 함수 역시 첫번째 링크를 통해서 학습한 내용이다. 다만, 여기에서 for문 안의 첫번째 if문을 보자. 링크에 있는 코드를 참조해서 구현을 했더니 예외가 발생한다. 위의 슬라이드에서 붉은색 음영처리가 되어있는 부분을 보자. i,j가 모두 4이다. 

이때, if문의 조건을 보면 j가 타겟배열의 마지막인덱스와 같아지면 무조건 return 하게 되어있다. 이것의 오류는 위의 상황에서 ababa를 찾아야하는데 대상의 ababc도 ababa로 보고 찾는 결과를 낳게된다. 따라서, 슬라이드의 오른쪽 아래와 같이 예외처리를 해주면된다. 대상배열과 타겟배열의 내용을 비교해서 같아야 return 하는 조건을 삽입 했다.

이 슬라이드는 비교함수의 디테일한 이해를 돕기위한 부분이다. i,j가 4,4인 부분에서 어떻게 5,0으로 변화하는지 또한 i,j가 5,0이 되었을 때, 대상배열과 타겟이 위치하는 모양새는 어떻게 되는지에 대한 내용이다. i,j가 4,4 -> 4,2 -> 4,0 -> 4,-1 -> 5,0 이 되어가는 과정을 위의 슬라이드와 같이 흐름을 이해한다면, 전체적인 알고리즘을 이해하는데 도움이 될 것이다.

작성자가 직접 java로 구현한 KMP알고리즘

->http://ict-nroo.tistory.com/17