효율적인 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 을 이해하고있느냐를 물어보는 문제인데..
위에 링크에도 대략 설명되어있다..


'Problem Solving > Algorithm notes' 카테고리의 다른 글

Articulation Points  (0) 2010.11.21
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23
Modular Exponentiation (Big Mod)  (2) 2010.02.19
KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15
Sorting Algorithm O(n^2)  (0) 2009.08.31
Bell Number  (0) 2009.07.12
Finding Minimum Path Cover in DAG  (0) 2009.06.15
Plane Equation (평면의 방정식)  (0) 2009.04.16
Ellipse (타원)  (0) 2009.04.15

Leave a Comment


to Top