나이브 문자열 매칭 알고리즘 (Naive String match algorithm)

패턴 검색은 컴퓨터 과학에서 중요한 문제이다.
패턴 검색이 필요한 사례들은 매우 많은데 메모장, 파일, 브라우저 또는 데이터베이스에서 문자열을 검색 할 때 패턴 검색 알고리즘으로 검색 결과를 표시하는 것이 그 예이다.

문제는 매우 긴 문자열에서 내가 찾고자 하는 문자열(패턴)을 어떻게 빠르고 정확하게 찾아낼수 있을까? 이다.

문자열에서 패턴을 검색하기 위해 다양한 알고리즘들이 있는데 그 중 나이브 문자열 매칭 알고리즘 (Naive String match algorithm)은 문자열 처음부터 끝까지 우리가 찾고자 하는 패턴과 일치하는지 하나씩 비교해가면서 단순 무식하게 문자열을 찾는다.

[출처] https://apprize.info/science/algorithms_2/7.html

예를들어 아래 표처럼 문자열 S = "THIS IS A TEST TEXT" 가 있고 찾고자 하는 패턴 P = "TEST" 가 있다고 하자.

S[0] 부터 패턴 전체와 일치하는지 확인한다.

S[1] = 'H' 와 P[1] = 'E' 와 일치하지 않기 때문에 S[1] 부터 다시 확인한다.

이렇게 하나씩 비교할 index 를 증가하면서 순차적으로 찾다보면 S[10] 번배 비교시 패턴과 일치하는 부분을 찾게 되는 것이다.