티스토리 뷰

알고리즘 이론

KMP Pattern Searching

museop 2017. 2. 20. 20:05

Knuth-Morris-Pratt Pattern Searching



긴 문자열 \(A\)(길이 \(M\))에서 특정 패턴 문자열 \(B\)(길이 \(N\))가 나타나는 모든 위치를 \(O(M + N)\) 시간에 찾아내는 알고리즘이다.


구현



예제


'알고리즘 이론' 카테고리의 다른 글

Modular Arithmetic  (0) 2017.03.18
탐색 (Searching)  (0) 2017.03.06
Counting Sort, Radix Sort  (0) 2017.02.23
Suffix Array, LCP Array  (0) 2017.02.22
트리의 지름 (Diameter of Tree)  (0) 2017.02.20
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/02   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함