티스토리 뷰

문제:icpc.me/11479


서로 다른 부분 문자열의 개수를 세는 문제이다.


Suffix Array를 이용하여 LCP Array를 구해준 뒤 


0~n 에 대하여 n-SA[i]-LCP[i](해당 Suffix의 길이-LCP) 의 합을 구해주면 된다.


해당 Suffix의 부분 문자열의 경우의 수는 해당 Suffix의 길이지만 이때 LCP만큼 중복되기 때문이다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long ll;
#define MAX_N 1000010
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) {
    if (g[x] == g[y]) {
        return g[x + t] < g[y + t];
    }
    return g[x] < g[y];
}
int main() {
    scanf("%s"&str);
    t = 1;
    n = (int)strlen(str);    
    for (int i = 0; i < n; i++) {
        SA[i] = i;
        g[i] = str[i] - 'a';
    }        
    while (t <= n) {    
        g[n] = -1;
        sort(SA, SA + n, cmp);    
        tg[SA[0]] = 0;
        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;
    }
    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--;
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (ll)(n - SA[i] - LCP[i]);
    }
    printf("%lld\n", ans);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)10266 시계 사진들  (0) 2017.02.08
BOJ)1305 광고  (0) 2017.02.08
BOJ)11479 서로 다른 부분 문자열의 개수2  (0) 2017.02.08
BOJ)9249 최장 공통 부분 문자열  (0) 2017.02.08
BOJ)5582 공통 부분 문자열  (0) 2017.02.08
BOJ)1605 반복 부분문자열  (0) 2017.02.08
댓글
댓글쓰기 폼