티스토리 뷰

문제: icpc.me/9249


http://jason9319.tistory.com/143와 유사한 문제이다.


두 문자열 사이에 더미를 끼운 뒤 하나로 연결한 후 LCP Array의 최댓값을 구하는데 이때 해당 LCP[i]를 구성하는 SA[i]와 SA[i-1]이 서로 다른 문자열에서 파생된 문자여야 한다.


거기에 해당 부분 문자열을 출력해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 200020
using namespace std;
char str[* MAX_N], str2[MAX_N], res[MAX_N];
int t, n, m, 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() {
    t = 1;
    scanf("%s%s"&str, &str2);
    m = strlen(str);
    str[m] = '!';
    strcat(str, str2);
    n = 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--;
        }
    }
    int ans = 0;
    for (int i = 1; i < n; i++) {
        if ((SA[i - 1]>&& SA[i] < m) || (SA[i - 1]<&& SA[i]>m)) {
            if (ans < LCP[i]) {
                ans = LCP[i];
                for (int j = 0; j < ans; j++)
                    res[j] = str[j + SA[i]];
            }
        }
    }
    printf("%d\n", ans);
    for (int i = 0; i < ans; i++)
        printf("%c", res[i]);
    return 0;
}
cs


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

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
BOJ)1021 회전하는 큐  (0) 2017.02.06
댓글
댓글쓰기 폼