×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,101,837명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

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
#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], RANK[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()
{
    int get;
    scanf("%d"&n);
 
    scanf("%s"&str);
    getSA(str);
 
    // r 배열에는 접미사 배열 순서가 들어간다.
    for (int i = 0; i < n; i++)
        RANK[SA[i]] = i;
 
    int len = 0;
 
    for (int i = 0; i < n; i++)
    {
        int k = RANK[i];
        if (k)
        {
            int j = SA[k - 1];
 
            while (str[j + len] == str[i + len])
                len++;
 
            LCP[k] = len;
 
            if (len)
                len--;
        }
    }
 
    sort(LCP, LCP + n);
 
    printf("%d", LCP[n - 1]);
 
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

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

[1916번] 최소비용 구하기  (0) 2017.02.27
[9248번] Suffix Array  (0) 2017.02.25
[1605번] 반복 부분문자열  (0) 2017.02.25
[4883번] 삼각 그래프  (0) 2017.02.24
[1890번] 점프  (5) 2017.02.24
[7489번] 팩토리얼  (0) 2017.02.24