자료구조 & 알고리즘

Pattern Searching 알고리즘

Drill_Labito 2023. 1. 7. 19:56

Reference : https://www.geeksforgeeks.org/algorithms-gq/pattern-searching/

 

Pattern Searching - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

 

패턴 탐색 ( Pattern Searching ) 알고리즘은 문자열 탐색 알고리즘에서 언급되는 알고리즘으로, 어떤 문자열에서 특정한 패턴을 찾기위해 쓰이는 알고리즘이라고 이해하면 된다. 

 

아래그림을 예시로 살펴보자.

 

위 그림을 보면, Text 로 들어온 문자열에서, 'AABA' 라는 문자패턴을 찾고싶다고 할 때, Text 문자열에서 해당 패턴이 나타나는 인덱스를 나타내면, Text 문자열의 0번째, 9번째, 12번째에서 나타난다. 

 

이런식으로 한 문자열에서, 어떠한 다른 문자열을 찾아내는 방식을 Pattern Searching 알고리즘이라고 하며, 알고리즘 종류는 다음과 같다. 

 

1. Naive Pattern Searching ( 무식하게 찾기 ) 

2. Rabin-Karp 알고리즘

3. KMP 알고리즘

4. Z 알고리즘 ( 선형 시간 pattern searching 알고리즘 ) 

5. Finite Automata ( 유한 오토마타 ) 알고리즘

6. Boyer Mooer 알고리즘

7. Suffix Array 

 

이제 다음 포스팅에서 이 알고리즘들에 대해 알아보자.