문자열 검색 알고리즘: KMP(Knuth-Morris-Pratt)

※ 이 글은 chatGPT를 기반으로 작성한 글입니다.

① KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색 알고리즘(string matching algorithm) 중 하나로, 특정 패턴 문자열을 찾기 위한 알고리즘이다.

  ㉠ 보이어-무어 알고리즘(boyer-moore algorithm)과 함께 가장 많이 사용되는 문자열 검색 알고리즘이다.

② 브루트 포스 방식을 이용하면 최악의 경우 O(N * M)의 시간 복잡도를 갖기 때문에 이를 사용하는 것은 효율적이지 않다.

 

브루트 포스

③ KMP 알고리즘은 패턴 문자열의 접두사와 접미사가 일치하는 최대 길이를 이용한다.

  ㉠ 패턴의 유사도를 측정하여 불필요한 패턴은 스킵하고, 효율적으로 탐색하겠다는 것이 KMP 알고리즘의 취지이다.

 

   

  ㉡ 이해를 돕기 위해 접두 부분과 접미 부분을 분리해서 보자.

    ⓐ BANANA에서 분리할 수 있는 접두, 접미 부분은 다음과 같다.

    ⓑ 접두 부분이 B이고, 접미 부분이 B이면 사전에 검사한 패턴과 사후에 검사한 패턴이 똑같기 때문에 겹치는 최대 길이는 0으로 간주한다.

 

    ⓒ 접두 부분이 B이고, 접미 부분이 A이면,

 

    ⓓⓔ

    ⓐ 접두사와 접미사가 일치한다는 것의 의미는 사전에 접두 부분에 위치한 패턴과 접미 부분이 서로 동일하단 것이다.

    ⓑ  왼쪽 배열과 오른쪽을 각각 접두, 접미로 가지고 있는 배열은 1만큼 동일한 패턴으로 인식한다

 

④ 패턴의 유사도

⑤⑥⑦⑧⑨⑩⑪⑫⑬⑭⑮
㉠㉡㉢㉣㉤㉥㉦㉧㉨㉩㉪㉫㉬㉭
ⓐⓑⓒⓓⓔⓕⓖⓗⓘⓙⓚⓛⓜ