문자열 매칭 (String Matching)

문자열 매칭 (String Matching)

텍스트에서 패턴 문자열을 찾는 알고리즘

목적: 패턴 검색, 텍스트 처리, 검색 엔진

특징: 전처리 유무, 단일/다중 패턴, 비교 방향에 따라 알고리즘 분류

분류: 단순 매칭, KMP, Rabin-Karp, Boyer-Moore, Aho-Corasick

주요 알고리즘: Naive(O(nm)), KMP(O(n+m)), Rabin-Karp(O(n+m) 평균), Boyer-Moore(평균 O(n/m))

적용사례: 텍스트 에디터 찾기, 검색 엔진, DNA 서열, 침입 탐지

비교: KMP(O(n+m)/최악보장/단일패턴) vs Boyer-Moore(평균빠름/뒤에서비교) vs Rabin-Karp(해시/다중패턴) vs Aho-Corasick(트라이/다중패턴/선형)

연관: KMP, Rabin-Karp, Boyer-Moore, Aho-Corasick, 문자열, 패턴