알고리즘 12강 (스트링 알고리즘)

학습개요

1. 이번 강의를 포함해서 앞으로 세 번의 강의를 통해서, 문자열을 의미하는 스트링에 대한 다양한 문제를 해결하는 스트링 알고리즘에 대해서 살펴본다. 우선 이번 시간에는 스트링 매칭 문제의 개념과 함께 다양한 스트링 매칭 알고리즘 중 라빈-카프 알고리즘과 KMP 알고리즘에 대해서 학습한다.

 학습목표

1. 스트링 및 스트링 매칭과 관련된 개념을 이해하고 설명할 수 있다.
2. 브루트-포스 스트링 매칭 알고리즘의 개념, 동작, 그리고 성능을 이해하고 설명할 수 있다.
3. 라빈-카프 알고리즘의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.
4. KMP 알고리즘의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.

 주요용어

1. 알파벳 (alphabet)
   스트링에 사용되는 문자들의 집합으로, 일반적으로 ∑로 나타냄
2. 스트링 매칭 (string matching)
   텍스트에서 패턴이 나타나는 위치를 찾는 문제
3. 브루트-포스 (brute-force) 스트링 매칭 알고리즘
   텍스트의 각 위치에서부터 패턴의 길이만큼 문자를 비교하며 매치를 찾는 방법
4. 라빈-카프 (Rabin-Karp) 알고리즘
   패턴의 해시값으로 매치의 후보를 찾고, 후보에 대해서만 문자별로 비교해서 매치를 찾는 방법
5. KMP (Knuth-Morris-Pratt) 알고리즘
   패턴 내의 문자들의 관계를 이용하여 매칭 시 중복된 비교를 줄이며 패턴을 찾는 방법으로, 패턴의 앞부분부터 문자를 비교

정리하기

1. 기본 개념
    ⦁ 스트링 → 문자가 연속적으로 나열된 문자열
    ⦁ 알파벳 → 스트링에 사용되는 문자들의 집합
    ⦁ 스트링 매칭 → 텍스트에서 패턴이 나타나는 위치를 찾는 문제
   - 텍스트 → 긴 스트링, 길이 n
   - 패턴 → 짧은 스트링, 길이 m
    ⦁ 브루트-포스 스트링 매칭 알고리즘
   - 텍스트의 각 위치에서부터 패턴의 길이만큼 문자를 비교하며 매치를 찾는 방법
   - 성능 → O(nm)
2. 라빈-카프 알고리즘
    ⦁ 패턴의 해시값으로 매치의 후보를 찾고, 후보에 대해서만 문자별로 비교해서 매치를 찾는 방법
    ⦁ 텍스트의 각 위치마다 해시값 계산이 필요하지만, 직전 위치의 해시값을 이용하여 상수 시간에 계산 가능
    ⦁ 성능 → O(n+km) (k: 매치의 개수)
    ⦁ 매치의 개수가 상수라면 O(n)이지만, 텍스트의 모든 위치에서 매치가 발생하면 O(nm)
3. KMP 알고리즘
    ⦁ 패턴 내의 문자들의 관계를 이용하여 매칭 시 중복된 비교를 줄이며 패턴을 찾는 방법
    ⦁ 텍스트의 첫 위치에서 패턴의 앞부분부터 문자 비교
    ⦁ 불일치가 발생하면 일치한 서브스트링에 대해, 매치를 찾으면 패턴 전체에 대해 접두부와 접미부의 최대 일치 정보를 이용하여 해당 크기만큼 패턴을 텍스트의 다음 위치로 옮김
    ⦁ 전처리 → 패턴의 각 위치별로 접두부와 접미부의 최대 일치 정보를 구함
    ⦁ 성능 → O(n)
    ⦁ 전처리에 O(m), 매칭에 O(n)