searching
-
[Algorithm] 알고리즘 - 문자열 매칭(Pattern Matching)Study/Algorithm 2020. 8. 27. 19:00
문자열 매칭 또는 패턴 매칭은 컴퓨터 과학에서 중요한 문제이다. 노트패드나 워드파일 또는 웹 브라우저 데이터베이스에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다. 문자열 매칭 방법의 종류는 아래와 같다. 1. Naive Matching (원시적인 매칭) - $O(mn)$ 2. Automata Algorithm (오토마타를 이용한 매칭) - $\Theta(n + |\sum| m)$ 3. Rabin-Karp Algorithm (라빈-카프 알고리즘) - $\Theta(n)$ 4. Knuth-Morris-Pratt(KMP) Algorithm (KMP알고리즘) - $\Theta(n)$ 5. Boyer-Moore Algorithm (보이어-무어 알고리즘) - $\Theta(n)$ Wor..