Algorithm Study (문자열)

이전내용 링크

 

완전탐색

정렬

 

 

4. 문자열

현대의 컴퓨터는 많은 양의 문자열 자료를 다루고 이를 처리하는것은 중요하다.

 

문자열 검색 문제는 주어진 문자열 H(건초, haystack)에서 문자열 N(바늘, needle)을 부분 문자열로 포함하는지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제를 문자열 검색 문제라고 한다. (건초에서 바늘찾기)

 

예) H = "network", N = "net" 일때 H[0..2] = N 이므로 H는 N을 포함하고, H에서 N의 시작 위치는 0이 된다.

예) H = "ababa", N= "aba" 일때, H[0..2] = H[2..4] = N 이므로 H는 N을 포함하고, H에서 N의 시작위치는 0, 2 가 된다.

 

위 문제를 Brute Force하게 풀면 N의 가능한 모든 위치를 다 시도해 보는 방법이 있다.

이 방법은 최악의 경우 시간 복잡도 O(|H| x |N|)를 가지게 된다.

입력이 클 경우 해당 알고리즘은 비효율 적이지만 이런 경우는 흔하지 않아서 표준 라이브러리의 구현은 Brute Force 하게 구성되어있다고 한다.

 

4-1. KMP 알고리즘(커누스-모리스-프랫(Knuth-Morris-Pratt)알고리즘)

앞의 알고리즘을 좀 더 효율적으로 풀기 위한 알고리즘이다.

 

|N| = 7이고 문자열 H에서 인덱스 i부터 비교하여 i+6번째에서 일치 하지 않았다고 할 때, i+1 부터 비교를 시작하지 않고 몇개의 인덱스를 건너 뛰어 비교하는 기법이다.

이때 건너뛰려는 부분에서 N의 접두사가 일치하는 문자열이 있을 수도 있다.

 

어떤 긴 문자열 H에서 N = "aabaabac" 을 찾는 경우 H[i..i+6]까지 일치하고 H[i+7]에서 불일치 한 경우

H[i..i+6] = "aabaaba" 이고 다음 시작 위치는 H[i+3], H[i+6]이 될 수 있다.

일치한 글자의 수는 0에서 |N| 사이의 정수이기 때문에 전처리 과정에서 이 정보를 미리 저장 해 놓을 수 있고 이를 활용한 알고리즘이 KMP 알고리즘이다.

 

KMP알고리즘은 전처리 과정에서 다음과 같이 정의되는 배열 pi[]를 계산 해 놓는다.

 

pi[i] = N[...i] 의 접두사도 되고 접미사도 되는 문자열의 최대 길이

 

pi[]는 N이 어디까지 일치했는지가 주어졌을때, 다음 시작 위치를 어디로 해야할지를 말해준다.

이를 부분 일치 테이블(partial match table)라고 한다.

 

4-2. LCP(Longest Common Prefix) 알고리즘

4-3. 맨버-마이어스 알고리즘 (접미사 배열 생성 알고리즘)