728x90

 0. [c++] 백준  - 


https://www.acmicpc.net/problem/9248


 1. 풀이


처음 이 문제를 접했을 때는 생각보다 간단하게 구현을 할 수 있을 것 같았다. 하지만, 내 기대와 같이 문제가 쉽게 해결되지 않았다.

문제의 입력은 최대 500,000 까지의 입력이여서, 시간복잡도를 신경써야하는 문제였다.


처음 구현을 할때, Suffix Array의 시간 복잡도는 O(nlgn)의 크기로 시간내에 구동이 가능하지만, LCP Array를 단순하게 구현하니 시간 초과를 받게 되었다.

처음 구현은 

1
2
3
4
5
6
7
8
9
int N = temp.size()
 
for (int i = 1; i < N; i++) {
    int count = 0;
 
    for(int j = suffixArray[i -1], k=0; temp[i + k] == temp[j + k]; k++);
    cout << count << " ";
        
}
cs

과 같이 구현하였는데, 이와 같이 구현하니 시간복잡도가 O(n^2)로 문제가 있었다.


이를 해결하기 위해서 생각을 해보았는데, KMP의 알고리즘을 생각해보면, 반복되는 계산을 줄이기 위해 pi라는 배열을 만들어 필요 없는 부분을 뛰어 넘어가는 구현을 하는 것을 보았었다.

이를 비슷하게 활용하면 되지 않을까? 라는 생각으로 나아갔다.


결과적으로 이러한 논리가 성립하였는데, LCP Array의 계산은 가장 긴 문자열부터 시작을 하는 것이었다.


 suffixArray에 담긴 가장 긴 문자열(size = N)과 그 아래 문자열(길이는 랜덤)을 비교한다. 그리고 일치한 문자열의 길이가 k(k는 0이 아닌 정수)라 가정하자.

 그 다음으로 긴 문자열(size = N-1)과 그 아래 문자열을 비교할 때, 그 길이는 최소 k-1가 되는 것을 보일 수 있었다.


뭐 이게 성립하는 이유는 suffixArray가 사전순으로 정렬이 되어있고, 자신의 아래에 있는 문자열은 자신과 첫 글자가 일치하는 부분이 없거나, 자신보다 더 긴 경우 2가지로 나뉘어진다.


문제에 banana예시를 생각해보면, 

a

ana

anana

banana

na

nana


뭐, 이런식으로 ana에서는 3, na에서는 2, a에서는 1이 ACP Array에 담기게 된다


이와 같은 논리로 문제를 해결 할 수 있도록 코드를 구현한 것은 아래 소스코드에 있다.




 2. 소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
 
using namespace std;
 
int pos[500001];
 
//각 접미사들의 첫 t글자를 기준으로 한 그룹 번호가 주어질 때,
//주어진 두 접미사를 첫 2*t글자를 기준으로 비교한다.
//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];
 
    }
};
 
 
////코드 20.10 접미사 배열을 계산하는 맨버와 마이어스의 알고리즘
 
//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];
    group[n] = -1;
    //결과적으로 접미사 배열이 될 반환 값. 이 배열을 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);
        sort(perm.begin(), perm.end(), compareUsing2T);
        //2t글자가 n을 넘는다면 이제 접미사 배열 완성!
        t *= 2;
        if (t >= n)
            break;
        //2t글자를 기준으로 한 그룹 정보를 만든다.
        vector<int> newGroup(n + 1);
        newGroup[n] = -1;
        newGroup[perm[0]] = 0;
        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;
}
 
 
 
//계산의 반복을 줄이기 위해 구상을 해보자.
//접두사의 길이를 비교할 때 매번 자기 아래의 수와 비교를 하는 방법이 존재한다.
//하지만, 필요 없는 반복이 계속된다는 느낌이 든다.
//이것은 KMP에서 pi배열과 비슷하게 계산을 줄일 수 있는 방법이 존재 할 것 같다.
//결과적으로 
vector<int> LCPArray(const string& S, const vector<int>& suffixArray) {
    int N = S.size();
    vector<int> ret(N, 0);
    //길이가 긴 순서대로 비교를 할 것이다.
    //이를 위해 순서대로 자신의 위치를 표시해주는
    //pos[]배열을 만들어주었다.
    for (int i = 0; i < N; i++)
        pos[suffixArray[i]] = i;
 
    for (int i = 0, k=0; i < N; i++, k=max(k-1, 0)) {
        //suffixArray의 마지막은 비교가 불가능하다.
        if (pos[i] == N - 1) continue;
 
        //바로 아래의 접미사와 비교해서 몇 개의 글자가 일치하는지 비교한다.
        for (int j = suffixArray[pos[i] + 1]; S[i + k] == S[j + k]; k++);
        ret[pos[i]] = k;
    }
    return ret;
}
 
 
int main() {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    string temp;
    cin >> temp;
    vector<int> suffix = getSuffixArray(temp);
    vector<int> LCP = LCPArray(temp, suffix);
    int N = temp.size();
    for (int i = 0; i < N; i++) {
        cout << suffix[i]+1 << " ";
    }
    cout << "\nx ";
    for (int i = 0; i < N-1; i++) {
        cout << LCP[i] << " ";
    }
 
 
    return 0;
}
 
 
 
 
 
 
 
 
cs


 3. 참고


- 맴버와 마이어스의 알고리즘 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.666~667

- LCP Array 구하는 알고리즘

https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=221028710658


질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!


저작자표시

'<백준> > |C++| hard' 카테고리의 다른 글

[c++]백준 3038 - 완전 이진 트리  (0) 2019.07.09
[C++] 백준 10217 - KCM Travel(다익스트라 활용)  (1) 2019.06.20
[c++] 백준 11657 - 타임머신(벨만-포드 알고리즘)  (0) 2019.05.29
[c++] 백준 1504 - 특정한 최단 경로(다익스트라, 벨만-포드 알고리즘)  (0) 2019.05.28
[c++] 백준 1865 - 웜홀(벨만-포드 알고리즘)  (0) 2019.05.28

+ Recent posts

티스토리툴바