KMP (Knuth-Morris-Pratt) Algorithm
Problem Solving/Algorithm notes 2009. 11. 15. 00:55
효율적인 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 을 이해하고있느냐를 물어보는 문제인데..
위에 링크에도 대략 설명되어있다..
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' 카테고리의 다른 글
| 점과 선분과의 거리 (2) | 2011.01.22 |
|---|---|
| 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 |
| 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 |
| Combination 개수 구하기 (Pascal's Triangle) (2) | 2009.02.07 |