[18-알고리즘] 문자열 탐색(String Match) 소개 - Naive string match

문자열 탐색(String Match)문제는 주어진 문자열에서 패턴 P를 찾는 것입니다.  패턴 문자를 오른쪽으로 한 칸씩 이동해 가면서 텍스트 문자와 하나씩 비교하는 것입니다. 

[그림 1] 이렇게 Text의 4번째에 찾으려는 ABAA 패턴이 존재함을 확인 할 수 있습니다.

이러한 방식을 Naive String match algorithm이라고 하고 다음과 같은 알고리즘입니다.

n ← length [T] // Text의 글자 길이

m ← length [P] // Pattern의 글자 길이
for s ← 0 to n - m do    // n - m + 1번 반복 
    if P[1 . . m] = T[s +1 . . s + m] // 현재 위치에서 pattern 글자가 text글자와 일치한지 확인한다.
        then return valid shift s

<Naive String match algorithm의 pesudo code>

Naive String match algorithm의 시간 복잡도는 O((n-m+1)m)입니다. (n은 text의 글자 길이, m은 patteren의 글자 길이)

본 알고리즘은 효율적인 알고리즘이라고 할 수 없습니다. 왜냐하면 매번 문자열을 비교할 때마다 얻게되는 정보를 다음 번 문자열 비교에서 사용하지 않기 때문입니다.

[그림2] Text의 맨 처음에 Pattern이 존재함을 확인 할 수 있습니다.

[그림3] Text의 두 번째 문자부터 패턴과 비교하면 패턴의 세 번째 A에서 Mismatch가 발생합니다.

[그림4] Text의 세 번째 문자부터 비교하면 패턴의 첫 번째 A에서 Mismatch가 발생합니다.

문자열 Text에서 패턴 AAAB가 존재한다면 두 칸, 세 칸 오른쪽으로 이동해도 패턴 AAAB와 같은 문자가 없다는 것을 알 수 있습니다. 이렇게앞에서 문자열 T를 비교하면서 얻은 결과를 오른쪽으로 이동해서 비교할 때 사용할 수 있다면 더 빠른 시간에 비교할 수 있다는 것을 알았습니다. 이를 통해서 좀 더 문자열 비교를 효율적으로 할 수 있습니다. 

그러면 이보다 더 빠른 시간내에 문자를 탐색하는 방법으로 다음과 같은 알고리즘이 있습니다.

[1] Robin-Karp algorithm

[2] String match with finite auomata 

[3] Knuth-Morris-Pratt algoritim

다음 포스팅에서 앞으로 차례대로 살펴 보겠습니다.