문자열 - 맨버 마이어스 알고리즘

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 20장 문자열에 나온 내용을 바탕으로 작성하였습니다.

 

개요

이전에 KMP알고리즘에 대해 알아 보았었다.그럼에도 문자열 문제는 쉽지 않다. 가장 최근 2020 카카오 코딩 테스트를 보면 문자열 문제가 시작부터 연달아 나옴을 알 수 있다. 그만큼 중요하면서도 어려운 유형이다. 이번에는 접미사를 통해 문자열 알고리즘을 좀 더 확장시켜 보려고 한다.

 

1. 접미사 배열

문자열을 다룰 때 빼놓을 수 없는 자료구조로 접미사 배열이 있다고 한다.

'문자열의 맥가이버 칼' 이라고도 부른다는데 한번 공부해 보도록 하자.

 

먼저 접미사 배열은 말 그대로 한 문자열의 모든 접미사들을 사전 순으로 배열에 저장해 놓은 것을 말한다.

이때 접미사들을 그대로 저장하면 문자열의 길이의 제곱에 비례하는 메모리가 필요하므로

접미사의 시작 위치를 담는 정수 배열로 구현한다.

 

experiment를 예로 들자.

아래는 experiment의 접미사 배열이다. 

i	A[i]	S[A[i] ... ]
0	2	ent
1	6	eriment
2	9	experiment
3	4	iment
4	3	ment
5	1	nt
6	7	periment
7	5	riment
8	0	t
9	8	xperiment

 

이러한 접미사 배열은 문자열 검색에도 사용된다.

집더미 문자열 H가 바늘 문자열 N을 포함한다면 항상 N은 H의 어떠한 접미사의 접두사라는 점을 이용한다.

 

즉 experiment에서 peri라는 문자열을 찾았다고 한다면 peri는 periment의 접두사이다.

모든 부분 문자열들에 대해 이 속성은 성립한다.

 

이러한 속성을 이용하여 H의 접미사 배열을 이진 탐색해서 N이 출현하는 위치를 찾을 수 있다.

 

시간 복잡도는 접미사 배열의 길이 |H|에서 이진 탐색을 하므로 O(log|H|)이고, 

각 문자열이 같은지 다른지 비교하는 데에 O(|N|)의 시간이 걸리므로

총 시간 복잡도는 O(|N|log|H|) 이다.

 

그렇다면 접미사 배열은 어떻게 생성할 수 있을까?

가장 간단한 방법은 일반적인 정렬 알고리즘을 사용하면 된다.

책에서는 [0, n-1] 범위의 정수를 모두 담은 정수 배열을 정렬하되, 이때 비교 함수로 접미사를 비교하게 만들었다.

다른 방법도 많지만 비교 함수를 구현해서 정렬하는 방법은 많이 다뤄보지 않았기 때문에

이번 기회에 한번 이 방법을 공부해 보고자 했다.

 

아래는 접미사 배열을 생성하는 코드이다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
//비교함수 - 두 접미사의 시작 위치가 주어질 때 앞에 오는 접미사를 판단
struct SuffixComparator { 
    const string& s;
    SuffixComparator(const string& s) :s(s) {}; //생성자 - 초기화 리스트로 멤버 s를 초기화 
    bool operator()(int i, int j) {
        //s.substr()대신 strcmp()를 쓰면 임시 객체를 만드는 비용이 절약된다.
        return strcmp(s.c_str() + i, s.c_str() + j) < 0; 
        //이때 c_str()는 string을 char *형으로 바꾸어 주어 strcmp()를 사용 가능하게 해줌
        //strcmp는 str1 < str2 일 때는 음수, > 일 때는 양수, == 일 때는 0을 반환 
    }
};
 
vector<int> getSuffixArrayNaive(const string& s) {
    //이름은 어렵지만 s의 접미사 배열을 계산하는 함수이다.
    vector<int>perm; //접미사 시작위치 담은 배열
    for (int i = 0; i < s.size(); ++i) {perm.push_back(i);}
    //정렬 알고리즘을 할 때 미리 만들어 놓은 비교함수로 비교하면 끝
    sort(perm.begin(), perm.end(), SuffixComparator(s));
    return perm;
}

중간에 SuffixComparator(const string& s) :s(s) {};라는 코드가 이해가 안돼서 찾아봤는데

생성자 이면서 초기화 리스트로 멤버 s를 초기화시킨다.

이는 생성자가 호출될 때 동시에 초기화시켜준다는 이점이 있다고 한다.

 

이 코드의 시간 복잡도를 알아보자.

우리가 흔히 쓰는 sort는 시간 복잡도가 O(nlogn) 임을 잘 알고 있다. 

하지만 이 코드는 비교 함수가 추가적으로 들어갔다.

이 비교 함수는 최대 두 문자열의 길이만큼 비교해야 하므로 시간 복잡도는 O(n)이다.

따라서 이 코드의 시간 복잡도는 둘의 곱인 O(n^2 logn) 임을 알 수 있다.

 

2. 맨버 - 마이어스의 알고리즘

위에서 알아보았던 접미사 배열을 생성하는 가장 간단한 코드는 특정 경우(ex. aaa..... aaaaa) 같은 경우에는 아주 오랜 시간이 걸릴 수 있다. 

그렇다면 알고리즘 대회나 코딩 테스트 같은 경우 모든 테스트 케이스를 통과하기에는 무리다.

이때 사용할 수 있는 알고리즘이 맨버 - 마이어스의 알고리즘이다.

 

이 알고리즘은 정렬을 여러 번 수행한다.

먼저 접미사의 첫 한 글자를 기준으로 정렬하고, 그다음으로는 두 글자, 네 글자, 여덟 글자... 순으로 정렬한다.

 

이때 궁금증이 들었다.

정렬을 이렇게 하면 오히려 더 많은 시간이 걸려야 되는 게 아닌가..?

책을 조금만 더 읽다 보면 답이 나온다.

 

책에는 "이전 정렬에서 얻은 정보를 이용해 두 문자열의 대소 비교를 O(1)에 할 수 있기 때문"이라고 나온다.

 

이 알고리즘을 차근차근 살펴보자.

 

먼저 첫 t글자를 기준으로 접미사들을 정렬한다.

그리고 각 접미사들을 첫 t글자가 같은 것들끼리 그룹으로 묶고, 각 그룹마다 0부터 번호를 매긴다.

이렇게 해서 배열 group []을 만든다. (이 때 group[i] = S[i...]가 속한 그룹의 번호)

group[]을 만드는 방법은 접미사들을 처음부터 순회하면서 이전 접미사의 첫 t글자와 다르다면 이전 접미사 그룹의 번호 +1을 하면 된다.

이제 첫 2t 글자를 기준으로 비교해 보자. 

먼저 첫 t글자를 비교했을 때 다르다면 바로 사전 순을 판단할 수 있다.

만약 같다면, 즉 같은 그룹에 속한다면 S [i+t...]와 S [j+t...]의 첫 t글자를 서로 비교하면 된다.

 

이렇게 한다면 O(nlogn)의 시간에 접미사들을 정렬할 수 있고,

다시 이들을 순회하면서 O(n) 시간에 그룹을 지을 수 있다고 한다.

 

먼저 group을 이용해 비교하는 비교 함수를 구현해 보자.

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
//첫 t글자로 묶인 그룹 정보를 이용해 첫 2t글자를 비교하는 비교자의 구현
/*각 접미사들의 첫 t글자를 기준으로 한 그룹 번호가 주어질 때, 
  주어진 두 접미사를 첫 2t글자를 기준으로 비교한다.
  group[]은 길이가 0인 접미사도 포함된다.*/
struct Comparator {
    const vector<int>& group;
    int t;
    Comparator(const vector<int>& _group, int _t) :group(_group), t(_t) {
        group = _group; //책에는 이렇게 나와있지만 operator에러. 없에도 됨
        t = _t;
    }
 
    bool operator()(int a, int b) {
        //첫 t글자가 다르면 이들을 이용해 비교한다.
        if (group[a] != group[b])return group[a] < group[b];
        //아니라면 S[a+t..]와 S[b+t..]의 첫 t글자를 비교한다.
        return group[a + t] < group[b + t];
    }
};

 

위의 코드는 책에 있는 코드이다.

생성자야 위에서 공부했기 때문에 그렇다 치고..

가장 이해가 안 된 부분은 return group [a+t] < group [b+t] 부분이다.

첫 t글자가 다르면 group을 이용해 비교하는 것은 알겠는데, 같으면 왜 a+t와 b+t를 비교하지?라고 생각했다.

 

오늘도 또 한 번 종 만북의 벽을 느끼며 구글링 하던 중..

내가 얼마나 대충 공부했는지 느꼈다. 

 

여기서 operator()의 매개 변수로 들어오는 a, b는 사실 suffix i, suffix j이다.

즉 suffix i = i 번째 index에서 시작되는 접미사, suffix j = j번째 index에서 시작되는 접미사이다.

이렇게 생각하면 저 부분이 당연하다.

 

group [a+t] 는 suffix a+t, 다시 말해 suffix a에서 t+1번째 부터 시작하는 접미사가 어디 그룹에 있는지를 알려준다.

 

결국 group[a+t] vs group [b+t]는 말 그대로 S [a+t...]와 S [b+t...]의 첫 t글자를 비교하는 것이다.

 

이제 이해가 되었으니 위의 비교자 코드를 사용한 전체 알고리즘을 살펴보자.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
//s의 접미사 배열을 계산한다.
vector<int>getSuffixArray(const string& s) {
    int n = s.size();
    //group[i]는 첫 t글자를 기준으로 정렬 했을 때 S[i..]가 들어가는 그룹 번호
    //t=1일 때는 정렬할 것도 없이 S[i..]의 첫 글자로 그룹 번호를 정해 줘도 같은 효과가 있다.
    int t = 1;
    vector<int>group(n + 1);
    for (int i = 0; i < n; ++i) group[i] = s[i]; //처음에는 1글자만 비교하므로 상관없음
    group[n] = -1; //길이가 0인 접미사를 예외처리
    //결과적으로 접미사 배열이 될 반환 값. 이 배열을 lg(n)번 정렬한다.
    vector<int>perm(n);
    for (int i = 0; i < n; ++i) perm[i] = i;
    while (t < n) {
        //group[]은 첫 t글자를 기준으로 계산해 두었다.
        //첫 2t글자를 기준으로 perm을 다시 정렬한다.
        Comparator compareUsing2T(group, t); //perm을 그룹을 기준으로 정렬하기 위함
        sort(perm.begin(), perm.end(), comapreUsing2T); //여기서 어차피 정렬 함. 
        t *= 2;
        if (t >= n)break; //2t 글자가 n을 넘는다면 이제 접미사 배열 완성
        //2t글자를 기준으로 한 새로운 그룹 정보를 만든다.
        vector<int>newGroup(n + 1);
        newGroup[n] = -1;
        newGroup[perm[0]] = 0;
        //내가 이해한 이 아래의 코드는 perm에서 다른그룹이라면(2t글자가 같지 않았다면)
        //그룹 번호를 +1 해줌으로써 그룹 번호 갱신하는 코드임
        for (int i = 1; i < n; ++i) {
            if (compareUsing2T(perm[i - 1], perm[i])) {
                newGroup[perm[i]] = newGroup[perm[i - 1]] + 1;
            }
            else
                newGroup[perm[i]] = newGroup[perm[i - 1]];
        }
        group = newGroup;
    }
    return perm;
}

 

추가 설명 : 내가 계속 이해가 안 된 부분인데 왜 처음에 group [i]=s [i]일까 생각해보다가
결론 ->  s [i]가 아스키코드로 저장됨. 즉 최대 95(a)까지 가능. 95같이 큰 수도 크게 문제가 되지 않는다.

 

예제 1 : 원형 문자열

길이가 n <=40000인 원형 문자열이 있다. 이 원형 문자열은 시작 위치가 정해져 있지 않다.

따라서 이 문자열들 중 가장 사전 순으로 앞에 오는 문자열은 무엇일까?

 

이 문제를 푸는 가장 단순하고도 쉬운 방법은 n개의 문자열을 비교하면 된다.

딱 봐도 시간 복잡도가 어마 무시할 것 같은데 계산해보면 

n개의 문자열을 n-1번 비교하기 때문에 O(n^2) 임을 알 수 있다.

즉 이 문제 같은 경우 40000의 제곱, 즉 최대 1600000000(16억) 번까지 계산해야 한다.

 

이 문제는 접미사 배열로 풀 수 있다.

바로 문자열 S를 두 번 반복한 S'으로 만들면 된다.

따라서 S'의 접미사 배열을 만든 뒤, 길이가 n이상인 접미사 중 가장 앞에 오는 것을 찾으면 된다.

이렇게 하면 시간 복잡도가 O(nlog^2n)이 된다.

 

코드는 아래와 같다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
string minShift(const string& s) {
    string s2 = s + s;
    vector<int> a = getSuffixArray(s2); //접미사 배열
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] <= s.size()) //시작 위치가 문자열의 길이보다 짧아야 길이가 가능
            return s2.substr(a[i], s.size()); //시작위치 부터 길이만큼 잘라서 반환
    }
}

 

즉 접미사 배열을 구한 뒤 시작 위치가 n과 같아지는 지점을 찾은 뒤 n만큼 반환하면 된다.

 

예제 2 : 서로 다른 부분 문자열의 수

길이가 n(n <=4000)인 문자열은 최대 (n*(n+1))/2개의 부분 문자열을 가질 수 있지만 서로 모두 다른 건 아니다.

예를 들면 "banana"는 "ana"와 "n"을 두 번씩 포함한다.

 

문자열이 주어질 때 이들의 서로 다른 부분 문자열의 수를 세는 문제를 풀어 보자.

 

이 문제도 가장 간단한 방법은 모든 부분 문자열을 C++의 set에 집어넣으면 된다.

알고 있다시피 set에 집어넣으면 자동으로 정렬된다.

시간 복잡도는 O(n^3 logn)이 된다. 

책에서는 해쉬를 사용하는 방법도 있다고 하지만 해쉬를 아직 공부하지 않았으므로 PASS

 

그렇다면 접미사 배열로 해결할 수 있을까?

정답은 YES! (그러니까 책에 소개가 되었겠지)

 

먼저 접미사 배열을 만든다.

이때 S의 모든 부분 문자열들은 접미사들의 접두사로 표현할 수 있다.

길이가 m인 접미사에는 m개의 접두사가 있을 테니, 부분 문자열 중 중복이 없다면 각 접미사의 길이를 모두 더해서 부분 문자열의 수를 얻을 수 있다.

처음에 책에서 이 문장을 보고 이해가 안 됐다.

길이가 m인 접미사에는 당연히 m개의 접두사가 있고, 부분 문자열 중 중복이 없다면 당연히 모든 접미사의 길이를 더하면 부분 문자열의 수이다. 

근데 이 둘을 같이 생각해 보려고 하니 도저히 방법이 떠오르지 않았다.

 

책에는 이렇게 나와있다.

한 부분 문자열이 두 번 이상 출현할 경우 이를 접두사로 갖는 접미사들은 접미사 배열 상에서 항상 인접해 있다.

따라서 어떠한 부분 문자열이 이미 출현했는지를 알기 위해서는 바로 윗 칸의 접미사만을 보면 된다.

 

사실 말로만 설명하면 이해가 잘 안 된다. 

바로 코드로 넘어가 보자.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
//S[i..]와 S[j..]의 공통 접두사의 최대 길이를 계산하는 함수
int commonPrefix(const string& s, int i, int j) {
    //생각보다 단순하게 구한다. 같으면 증가시키면 끝
    int k = 0;
    while (i < s.size() && j < s.size() && s[i] == s[j]) {
        ++i; ++j; ++k;
    }
    return k;
}
 
//s의 서로 다른 부분 문자열의 수를 센다
int countSubstrings(const string& s) {
    vector<int>a = getSuffixArray(s);
    int ret = 0;
    int n = s.size();
    for (int i = 0; i < a.size(); ++i) {
        int cp = 0;
        if (i > 0)cp = commonPrefix(s, a[i - 1], a[i]);
        //a[i]의 (n-a[i])개의 접두사들 중에서 cp개는 중복이다.
        ret += n - a[i] - cp;
    }
    return ret;
}

 

코드를 보니 생각보다 간단하다.

말 그대로 접미사 배열을 구하고, 접미사 배열을 순환하면서 윗 칸의 접미사와 공통인 부분이 얼만지만 찾아서 빼주면 된다.

이 코드의 시간 복잡도는 O(n^2)이다.

 

문제 : 말버릇 (문제 ID : HABIT)

algospot.com/judge/problem/read/HABIT

algospot.com :: HABIT

문제를 요약해 보자면 n번 이상 등장하는 길이가 가장 긴 문자열의 길이를 출력하라 이다.

 

말은 쉽지.. 아무리 봐도 답이 안 보인다.

결국 책을 보고 풀었다.

 

책의 풀이 방법은 아래와 같다.

위에서 공부했듯이 만약 문자열이 중복된다면 접미사 배열에서 인접해 있을 것이다.

그렇다면 모든 접미사 배열을 돌면서 그 안에서 suffixArray [i]부터 suffixArray [i+n-1]까지를 순환하면서 공통부분 문자열의 길이가 몇인지를 비교하면 된다.

그리고 그러한 공통 부분 문자열의 길이중 가장 긴 값, MAX값을 출력하면 된다.

코드는 아래와 같다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
//첫 t글자로 묶인 그룹 정보를 이용해 첫 2t글자를 비교하는 비교자의 구현
/*각 접미사들의 첫 t글자를 기준으로 한 그룹 번호가 주어질 때,
  주어진 두 접미사를 첫 2t글자를 기준으로 비교한다.
  group[]은 길이가 0인 접미사도 포함된다.*/
struct Comparator {
    const vector<int>& group;
    int t;
    Comparator(const vector<int>& _group, int _t) :group(_group), t(_t) {}
 
    bool operator()(int a, int b) {
        //첫 t글자가 다르면 이들을 이용해 비교한다.
        if (group[a] != group[b])return group[a] < group[b];
        //아니라면 S[a+t..]와 S[b+t..]의 첫 t글자를 비교한다.
        return group[a + t] < group[b + t];
    }
};
 
//s의 접미사 배열을 계산한다.
vector<int>getSuffixArray(const string& s) {
    int n = s.size();
    //group[i]는 첫 t글자를 기준으로 정렬 했을 때 S[i..]가 들어가는 그룹 번호
    //t=1일 때는 정렬할 것도 없이 S[i..]의 첫 글자로 그룹 번호를 정해 줘도 같은 효과가 있다.
    int t = 1;
    vector<int>group(n + 1);
    for (int i = 0; i < n; ++i) group[i] = s[i]; //처음에는 1글자만 비교하므로 상관없음
    group[n] = -1; //길이가 0인 접미사를 예외처리
    //결과적으로 접미사 배열이 될 반환 값. 이 배열을 lg(n)번 정렬한다.
    vector<int>perm(n);
    for (int i = 0; i < n; ++i) perm[i] = i;
    while (t < n) {
        //group[]은 첫 t글자를 기준으로 계산해 두었다.
        //첫 2t글자를 기준으로 perm을 다시 정렬한다.
        Comparator compareUsing2T(group, t); //perm을 그룹을 기준으로 정렬하기 위함
        sort(perm.begin(), perm.end(), compareUsing2T); //여기서 어차피 정렬 함. 
        t *= 2;
        if (t >= n)break; //2t 글자가 n을 넘는다면 이제 접미사 배열 완성
        //2t글자를 기준으로 한 새로운 그룹 정보를 만든다.
        vector<int>newGroup(n + 1);
        newGroup[n] = -1;
        newGroup[perm[0]] = 0;
        //내가 이해한 이 아래의 코드는 perm에서 다른그룹이라면(2t글자가 같지 않았다면)
        //그룹 번호를 +1 해줌으로써 그룹 번호 갱신하는 코드임
        for (int i = 1; i < n; ++i) {
            if (compareUsing2T(perm[i - 1], perm[i])) {
                newGroup[perm[i]] = newGroup[perm[i - 1]] + 1;
            }
            else
                newGroup[perm[i]] = newGroup[perm[i - 1]];
        }
        group = newGroup;
    }
    return perm;
}
 
int commonPrefix(const string& s, int i, int j) {
    //생각보다 단순하게 구한다. 같으면 증가시키면 끝
    int k = 0;
    while (i < s.size() && j < s.size() && s[i] == s[j]) {
        ++i; ++j; ++k;
    }
    return k;
}
 
int main() {
    string str;
    int t, n;
    cin >> t;
    //n번 이상 등장하는 길이가 가장 긴 문자열
    while (t--) {
        cin >> n;
        cin >> str;
        vector<int> a = getSuffixArray(str);
        int ret = 0;
        for (int i = 0; i + n <= str.size(); ++i) {
            ret = max(ret, commonPrefix(str, a[i],a[i + n - 1]));
        }
        cout << ret << "\n";
    }
}

솔직히 열심히 공부했지만 아직도 응용하기에는 어렵다..

천재가 아닌 이상 문제를 많이 풀어보는 방법밖에는 없는 것 같다.