티스토리 뷰

알고리즘 관련/BOJ

BOJ)13576 Prefix와 Suffix

JASON 자손9319 2017. 3. 13. 02:47

문제: icpc.me/13576


prefix와 suffix가 같은 모든 부분문자열은 pi배열을 이용하여 전부 구해줄 수 있다. length -> pi[length] -> pi[[pi[length]]] ... 이런식으로 


하지만 이때 부분 문자열의 등장횟수도 구해줘야 한다. suffix의 부분 문자열 등장횟수는 LCP를 이용하여 O(N)에 처리해줄 수 있다.


현재 확인중인 i번째 suffix의 등장횟수는 LCP[i+1]~ LCP[max] 중에서 연속으로 부분 문자열 i의 길이보다 큰 LCP의 개수로 처리해줄 수 있다.


아래 코드에서 dp배열에 suffix의 등장횟수가 담긴다.


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
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;
vector<int> pi;
string a;
int t, g[100001], tg[100001], SA[100001], r[100001], LCP[100001];
vector<pair<intint>> res;
bool cmp(int x, int y) {
    if (g[x] == g[y])return g[x + t] < g[y + t];
    return g[x] < g[y];
}
void getpi() {
    pi.resize(a.length());
    int j = 0;
    for (int i = 1; i < a.length(); i++) {
        while (j&&a[i] != a[j])
            j = pi[j - 1];
        if (a[i] == a[j])
            pi[i] = ++j;
    }
}
int dp[100005];
int func(int x) {
    int &ret = dp[x];
    if (ret != -1)return ret;
    ret = 1;
    for (int i = x + 1; i < a.length(); i++) {
        if (LCP[i] >= a.length() - SA[x]) {
            ret += func(i);
            i += func(i) - 1;
        }
        else break;
    }
    return ret;
}
int main() {
    memset(dp, -1sizeof(dp));
    cin >> a;
    getpi();
    t = 1;
    for (int i = 0; i < a.length(); i++) {
        SA[i] = i;
        g[i] = a[i] - 'A';
    }
    while (t <= a.length()) {
        g[a.length()] = -1;
        sort(SA, SA + a.length(), cmp);
        tg[SA[0]] = 0;
        for (int i = 1; i < a.length(); 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 < a.length(); i++)
            g[i] = tg[i];
        t <<= 1;
    }
    for (int i = 0; i < a.length(); i++)
        r[SA[i]] = i;
    int len = 0;
    for (int i = 0; i < a.length(); i++) {
        int k = r[i];
        if (k) {
            int j = SA[k - 1];
            while (a[j + len] == a[i + len])
                len++;
            LCP[k] = len;
            if (len)len--;
        }
    }
    for (int i = 0; i < a.length(); i++)
        func(i);
    res.push_back({ a.length(),});
    int x = pi[a.length() - 1];
    while (x) {
        int idx = r[a.length() - x];
        res.push_back({ x,dp[idx] });
        x = pi[x - 1];
    }
    printf("%d\n", res.size());
    for (int i = res.size() - 1; i >= 0; i--)
        printf("%d %d\n", res[i].first, res[i].second);
    return 0;
}
cs


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

BOJ)2311 왕복 여행  (0) 2017.03.13
BOJ)8892 팰린드롬  (0) 2017.03.13
BOJ)13576 Prefix와 Suffix  (0) 2017.03.13
BOJ)13506 카멜레온 부분 문자열  (0) 2017.03.12
BOJ)1585 경찰  (0) 2017.03.11
BOJ)4716 풍선  (0) 2017.03.11
댓글
댓글쓰기 폼