-
[Algorithm] Knuth-Morris-Pratt (KMP) 알고리즘
효과적인 설명을 위해 notation은 다음과 같다.x: 찾고자 하는 문자열m: x의 길이y: 본문의 문자열n: y의 길이 Morris-Pratt 알고리즘은 패턴 매칭을 하는데 유용한 알고리즘 중 하나다. Shift OR 함수처럼 매칭 시작전에 lookup table을 만드는 작업이…
-
[Algorithm] Pattern Matching
패턴매칭은 우리가 평소에 작업을 할 때 많이 사용한다. 예를 들면 strstr() 함수라던지 vim에서 / 동작, word에서 Ctrl+F 등 많은 utility에서 사용되고 있다. 패턴 매칭을 위해서 많은 loop을 돌아야하기 때문에 시간 복잡도는 O(n*m)이 된다.…
