KMP (Knuth-Morris-Pratt) Algorithm

효율적인 string matching 알고리즘이 필요한 경우 내가 주로 사용하는 방법으로 KMP 가 있다..
string N 에서 string M 을 찾고자 할때 O(|N|+|M|) 만에 찾을 수 있는 매우 강력한 방법이다..

기본 개념은.. 오토마타의 원리를 이용하는데..
matching 인지 검사해보고 틀리면 특정 위치로 이동해서 거기서부터 검사하는 방법이다..
mismatch 가 일어날 경우 이동하는 위치는 failure function 이란 걸 통해서 미리 만들어둔다..

그동안 대략적인 개념만 알뿐.. 필요한경우 그냥 복.붙 하면서 썼는데..
최근에 LA 3026 - Period 문제를 풀다가 된통 당했다.. ㅠ_ㅠ;;
아.. 역시.. 알고리즘을 아닌게 아는게 아니구나 느끼고.. 다시 KMP 를 공부하기 시작.. ㅠ_ㅠ;

KMP 에 대한 자세한 내용은 아래 링크에 잘 설명되어있다..
Introduction to String Searching Algorithms

3026 - Period 문제는 failure function 을 이해하고있느냐를 물어보는 문제인데..
위에 링크에도 대략 설명되어있다..