반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. LCP

2. Suffix Array


Suffix Array를 이해하고, Suffix Array를 구현하고 그 구현한 Suffix Array로 LCP를 구현할 수 있어야만 풀 수 있는 문제이다.


Suffix Array :: http://www.crocus.co.kr/613


LCP algorithm :: http://www.crocus.co.kr/614



소스 코드 : 


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
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 600000
using namespace std;
char str[MAX_N];
int t, n, g[MAX_N], tg[MAX_N], SA[MAX_N], r[MAX_N], LCP[MAX_N];
 
bool cmp(int x, int y)
{
    // 현재 보고있는 단어가 같으면 t번째 기준으로 정렬
    if (g[x] == g[y])
        return g[x + t] < g[y + t];
 
    // 현재 보고있는 단어가 다르다면 바로 정렬
    return g[x] < g[y];
}
void getSA(const char* str)
{
    t = 1;
    n = (int)strlen(str);    //글자의 수 배정
 
    //첫 글자에 의한 그룹을 정해주는 전처리
    for (int i = 0; i < n; i++)
    {
        SA[i] = i;
        g[i] = str[i] - 'a';
    }
 
    //1,2,4,8... 씩 단어의 길이보다 작은 경우를 탐색
    while (t <= n)
    {
        g[n] = -1;
        sort(SA, SA + n, cmp);    //그룹에 의한 정렬
        tg[SA[0]] = 0;    //다음 그룹을 할당하기 위하여 tempgroup의 첫번째 번호 배정
 
                        //다음 그룹 배정 
        for (int i = 1; i < n; i++)
        {
            //그룹이 다를 경우 다음 그룹 번호 할당
            if (cmp(SA[i - 1], SA[i]))
                tg[SA[i]] = tg[SA[i - 1]] + 1;
 
            //그룹이 같을 경우 같은 그룹 번호 할당
            else
                tg[SA[i]] = tg[SA[i - 1]];
        }
 
        //새로운 그룹 할당
        for (int i = 0; i < n; i++)
            g[i] = tg[i];
 
        t <<= 1// t *= 2;
    }
}
int main()
{
    scanf("%s"&str);
    getSA(str);
 
    // r 배열에는 접미사 배열 순서가 들어간다.
    for (int i = 0; i < n; i++)
        r[SA[i]] = i;
 
    int len = 0;
 
    for (int i = 0; i < n; i++)
    {
        int k = r[i];
        if (k)
        {
            int j = SA[k - 1];
 
            while (str[j + len] == str[i + len])
                len++;
 
            LCP[k] = len;
 
            if (len)
                len--;
        }
    }
 
    for (int i = 0; i < n; i++)
        printf("%d ", SA[i] + 1);
 
    printf("\n");
    for (int i = 0; i < n; i++)
    {
        if (!i)
            printf("x ");
        else
            printf("%d ", LCP[i]);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[2583번] 영역 구하기  (0) 2017.02.27
[1916번] 최소비용 구하기  (0) 2017.02.27
[1605번] 반복 부분문자열  (0) 2017.02.25
[4883번] 삼각 그래프  (0) 2017.02.24
[1890번] 점프  (5) 2017.02.24