[종만북] 문자열

hhyeong_0·2023년 8월 25일

[종만북] 알고리즘 정리

목록 보기

3/3

문자열 검색 알고리즘

: 타겟 문자열 H(avava)이 '패턴 문자열 N(ava)'을 부분 문자열로 포함하는지 확인하고자 하는 목적으로 한다.

1. 가장 간단한 알고리즘

모든 시작 위치에서 찾고자하는 문자열을 한번씩 모두 비교하는데, 불일치가 발생하면 그 시작지점은 break하고 다음 시작지점을 확인하는 방식

이 방식은 O(|H 문자열| * |N 문자열|)의 시간복잡도를 가짐

입력이 큰 경우엔 꽤 비효율적이지만, 이런 경우는 흔치 않으며 구현이 단순하다는 장점이 있기 때문에 단순한 알고리즘은 표준 라이브러리의 구현에 널리 사용된다
Ex) C의 strstr(), C++의 string::find(), 자바 문자열의 indexOf()
~~매우 비효율적인 라이브러리들이였구만~~

2. KMP 알고리즘

: "검색 과정에서 얻은 정보를 버리지 않고 잘 활용하면 많은 시간을 절약할 수 있다" 라는 아이디어를 기반한 알고리즘

- 먼저 KMP 알고리즘을 이해하기 위해 두가지 개념에 대한 이해가 필요하다.

1. 접두사(prefix)와 접미사(suffix)

<banana의 접두사>
b
ba
ban
bana
banan
banana
이 6개가 banana의 접두사(prefix) 입니다.

<banana의 접미사>
a
na
ana
nana
anana
banana
이 6개가 banana의 접미사(suffix) 입니다.

2. pi 배열 (부분 일치 테이블)

: pi[i]는 주어진 문자열의 0~i 까지의 부분 문자열 중에서 접두사와 접미사가 같은 부분 문자열 중 최대 길이이다.
~~말로는 이해가 힘들테니 아래 예시를 보자~~

Ex) 문자열 "ABAABAB"의 pi배열

Ex) "AABAA"의 pi배열

이 두가지 개념을 활용하면 앞서 검색에서 얻은 결과를 다음 검색때 활용하면 탐색의 효율성을 높일 수 있다.
아래의 예시를 보며 어떻게 활용할 수 있는지 확인해보자.

목표 : "ABCDABCDABEE"에서 패턴 "ABCDABE"를 찾기

첫번째 탐색 결과 :첫번째 탐색을 통해 ABCDAB 까지 일치하고 마지막 E는 일치하지 않았음을 확인.

단순한 알고리즘

단순한 알고리즘은 다음 탐색에서 아래와 같이 바로 다음 인덱스에서 다시 문자열이 패턴의 처음부터 일치하는지 확인한다.ㄴ 이는 앞선 검색에서텍스트 얻은 결과를 전혀 활용하지 않은 방식이다!

우리는 첫번째 탐색에서 인덱스[0-5]까지는 일치했다는 정보를 알고 있다.
=> 이를 활용하여 검색 속도를 개선하는 것이 바로 KMP 알고리즘의 핵심이다
이를 활용하면 다음 시도때 위에서 본 탐색 시도가 아닌 아래와 같이 탐색을 하게된다.
(i는 텍스트의 현재 비교위치, j는 패턴의 현재 비교위치를 나타내는 변수)
이것이 가능한 이유는 첫번째 탐색에서 일치했던 부분인 "ABCDAB"에서 파란색 박스로 표시한 접두사(prefix) AB와 접미사(suffix) AB가 일치하기 때문이다.
즉, 탐색 문자열의 앞 부분(접두사)과 원본 문자열의 뒷부분(접미사)이 동일한 부분까지는 문자열 탐색을 건너뛸 수 있다는 의미이다!

이렇게 KMP 알고리즘은 비교의 결과가 조금이라도 일치했었다는 정보에 주목하여, 미리 전처리 해둔 pi배열을 이용해 불필요한 중간 시도들을 생략할 수 있게한다.
~~(pi 배열을 전처리해야하는 것은 바로 윗 부분의 이유때문)~~
이 과정들이 KMP 알고리즘의 전반적인 원리이다.

아래는 전반적인 동작 과정을 전부 적어본 예시니 이해가 안갔다면 참고해보자!

이제 KMP 알고리즘을 구현한 코드를 살펴보자.

kmpSearch 함수
vector<int> kmpSearch(string& src, string& search){
    int n = src.size(), m = search.size();
    vector<int> ret;
    // 탐색할 문자열의 접두사, 접미사 길이를 문자열의 처음부터 끝까지 미리 계산
    vector<int> pi = getPartialMatch(search);    
    int begin = 0, matched = 0;
    while(begin <= n - m){
        // 탐색할 문자열과 원본 문자열에서 현재 위치의 문자가 동일한 경우
        if (matched < m && src[begin + matched] == search[matched]){
            ++matched;
            // 문자열이 모두 일치하는 경우
            if (matched == m)
                ret.push_back(begin);
        }
        else{
            // 일치하는 부분이 없는 경우, 다음 위치의 문자 부터 탐색
            if(matched == 0)
                ++begin;
            // 문자열이 불일치 하므로 접두사, 접미사의 길이만큼 건너 뜀!
            else{
                // 현재 불일치가 발생한 위치는 begin + matched
                // 여기서 접두, 접미사의 길이인 pi[matched - 1] 을 빼주면 다음 탐색 시작 위치
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return ret;
}
: 위에서 쓰인 getPartialMatch() 함수는 탐색 문자열의 접두사, 접미사의 길이를 구해주는 함수(즉, pi 배열을 생성하는 함수)입니다.
위 코드에서 탐색을 진행 하다 탐색 문자열의 5번째 문자에서 불일치가 발생했다면, pi[5 - 1] 처럼 5번째 문자 앞의 가장 긴 접두, 접미사의 길이를 받아온 후 그만큼 건너뛴 후 탐색을 다시 진행하게 된다.

문자열 불일치가 발생했다면, 현재 탐색하고 있는 문자의 위치는 원본 문자열을 기준으로 begin + matched 가 된다.

따라서 begin 에다가 matched 를 더해준 뒤, pi[matched - 1] 를 빼주면 KMP 알고리즘의 아이디어대로 접두, 접미사가 일치하는 다음 탐색 위치를 한번에 얻을 수 있게 됨.

getPartialMatch 함수
vector<int> getPartialMatch(string& search){
    int m = search.size();
    vector<int> pi(m, 0);
    int begin = 1, matched = 0;
    while(begin + matched < m){
        // 탐색 문자열과 탐색 문자열 자신을 매칭시킴!
        if(search[begin + matched] == search[matched]){
            matched++;
            pi[begin + matched - 1] = matched;	// 매칭을 진행하면서, 접두 접미사 배열을 바로 갱신
        }
        else{
            if(matched == 0)
                begin++;
            else{
                // KMP 문자열 탐색 알고리즘과 동일하게 불일치 발생 시
                // 매칭을 진행하면서 구했던 접두사 접미사 길이만큼 탐색을 건너뛸 수 있다
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }   
    return pi;
}
: KMP 알고리즘을 pi 배열을 구하는 과정에서도 동일하게 적용할 수 있다!
위의 과정을 잘 살펴보면 탐색문자열에 대해서 앞뒤로 탐색문자열 자신을 매칭시키는 과정이라는 것 을 알 수 있다.
따라서 문자열 매칭 과정과 본질적으로 다르지 않다.

KMP 알고리즘의 시간 복잡도

문자열 매칭이 항상 탐색 문자열의 마지막 문자 직전까지는 성공하고, 마지막 문자에 실패하는 경우가 최악의 상황일 것이다.

이때 시간 복잡도는 어떻게 될까?

1. 우선 matched 가 탐색 문자열의 길이 - 1 만큼 증가한다.

2. 그 후 문자열 불일치가 탐색 문자열의 마지막 문자에 발생하였으므로, matched = pi[matched - 1] 로 접두 접미사의 길이만큼 계속 감소한다.

이때 pi의 값(접두사, 접미사가 일치하는 최대길이)은 항상 현재 탐색 문자열의 길이보다 작으므로 matched만큼 계속 감소하면 결국 0이 된다.

위의 1, 2번 과정이 진행되면 begin의 위치는 얼만큼 바뀌었을까?

begin += matched - pi[matched - 1] 가 반복되고 pi[matched - 1]는 0에 가까워지므로, 결국 begin 은 begin + matched 에 위치하게 된다.

따라서 KMP 알고리즘의 최악의 경우 1번 과정에서 matched가 탐색 문자열의 길이-1 만큼 증가한 후, 2번 과정에서 최대 matched만큼 감소 한 결과 begin이 begin + matched 만큼 이동하였다는 것 을 알 수 있다.

즉, begin 이 begin + matched 로 이동하는데 최악의 경우에도 과정1 + 과정 2 = matched * 2 회 만큼 소요된다는 것이다.

따라서 KMP 알고리즘의 시간 복잡도는 탐색하고자 하는 문자열의 길이에 비례하게 된다.

타겟 문자열의 길이가 N, 패턴 문자열의 길이가 M 이라면 최종적인 시간 복잡도는 O(N + M) 이 되는것이다.