[문자열] 문자열 패턴 매칭

문자열 패턴 매칭

• 패턴 매칭에 사용되는 알고리즘
  
  
• 고지식한 패턴 검색 알고리즘 ( 브루트 포스 ) : 하나씩 확인하는 고지식한 패턴으로 최악의 경우에는 모든 텍스트의 위치에서 패턴을 비교해야 하므로 시간 복잡도가 O(MN)이다.

• 라빈-카프 알고리즘 : 문자열 검색을 위해 해시 값 함수를 이용하는 방식, 최악의 경우 시간 복잡도가 O(MN)이지만 평균적으로는 선형에 가까운 속도를 가진다. 해쉬값을 구하는 과정에서 일정 자리수가 넘어가게 되면 MOD연산을 통해 자리수를 줄이게 된다. -> 해시 충돌이 발생할 수 있다.
• 보이어-무어 알고리즘 : 끝까지 비교해서 틀리는 경우를 방지하기 위해 오른쪽에서 왼쪽으로 비교 최악의 시간 복잡도는 O(MN)이지만 최선의 시간 복잡도는 O(N/M)으로 평균적으로 가장 빠른 속도를 가짐

• KMP 알고리즘 ( Knuth-Moriris-Pratt ) : 불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행. → 접두사와 접미사의 개념을 사용하여 실패 함수를 작성
  • 패턴을 이용해서 실패함수 작성 -> 매칭이 실패했을 때 패턴 포인터가 돌아갈 곳을 계산
  • 패턴의 0번째 인덱스를 제외한 각 인덱스 마다 맨 앞부터 해당한다.
  • 인덱스까지의 부분 문자열 중 접두사와 접미사가 일치하는 최대 길이로 계산하여 작성한다.
  • 시간 복잡도는 O(M+N)