Pattern Matching & Pattern Finding(패턴 매칭)

Single Pattern Matching(단일 패턴 매칭):

Exhaustive Search: 이 방법은 모든 가능한 위치에서 패턴을 텍스트와 비교하여 일치하는 부분을 찾습니다.  시간 복잡도는 O(nm)입니다(n: 텍스트 길이, m: 패턴 길이).

DFA-Based Pattern Matching: Deterministic Finite Automaton(DFA)을 이용하여 패턴을 찾는 알고리즘입니다. 패턴과 일치하는 상태를 통해 문자열을 훑어내려갑니다.  전처리 시간 복잡도는 O(m)이고 검색 시간 복잡도는 O(n)입니다. => O(m) + O(n)

KMP Algorithm: Knuth-Morris-Pratt 알고리즘은 전처리를 통해 패턴의 정보를 활용하여 불필요한 비교를 줄입니다. 전처리 시간 복잡도는 O(m)이고 검색 시간 복잡도는 O(n)입니다. => O(m) + O(n)

Multiple Pattern Matching(다중 패턴 매칭):

AC Algorithm: Aho-Corasick 알고리즘은 트라이 자료구조와 상태머신을 활용하여 여러 패턴을 동시에 검색합니다. 전처리 시간 복잡도는 O(M)이고 검색 시간 복잡도는 O(n)입니다(M: 패턴 총 길이). => O(m) + O(n)

Weiner’s Algorithm: 워너의 알고리즘은 문자열 트리를 사용하여 여러 패턴을 빠르게 검색합니다. 전처리 및 검색 시간 복잡도는 O(n)입니다.

Approximate Pattern Matching: 

이 방법은 패턴과 완전히 일치하지 않더라도 일정한 허용 오차 범위 내에서 유사한 부분을 찾습니다. 알고리즘의 복잡도는 사용된 기법에 따라 다릅니다.

Exact Pattern Finding: 

텍스트에서 패턴과 정확히 일치하는 모든 부분을 찾는 알고리즘입니다. 시간 복잡도는 사용된 기법에 따라 다릅니다.

Frequent Pattern Finding: 

텍스트에서 가장 빈번하게 나타나는 패턴을 찾는 알고리즘입니다. 이를 위해 다양한 데이터 마이닝 및 문자열 처리 알고리즘이 사용됩니다.

Longest Pattern Finding: 

텍스트에서 가장 긴 패턴을 찾는 알고리즘입니다. 이 문제는 가장 긴 공통 부분 문자열(Longest Common Substring) 문제로 고려할 수 있으며, 다양한 다이나믹 프로그래밍 및 분할 정복 기법이 사용됩니다.

Approximate Pattern Finding: 

패턴과 유사한 정도에 따라 패턴을 찾는 알고리즘