kmp algorithm

string match알고리즘 인데 key는 한번 비교한 문자에 대해서 다시 비교하지 않는다이다.


ABCDABD에서  ABD를 검색한다고 하자.

0123456
ABCDABD : S[i]
ABD     : P[j]

- 2에서 처음 mismatch가 발생하는데, 이때 i는 3으로 바로 건너띌 수 있다. 왜냐하면 B로 시작하거나 C로 시작하면서 ABD와 match가 될수는 없기 때문에, 

반대로 
0123456789
ABADABABAC : S[i]
ABABAC     : P[j]
  ABABAC

이 경우는 3에서 mismatch가 발생하면, j를 1로 reset해서 다시 검색한다. ABAB에는 실패했지만 ABXX에서 성공할 수 있으므로.

앞에서 알아본 것을 구현하려면 failiure function을 미리 계산해서 가지고 있으면 된다.
N이 클 수록 시간에서 엄청난 이득을 볼 수 있다.

Reference:
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm#Description_of_and_pseudocode_for_the_search_algorithm
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching