티스토리 뷰

알고리즘 관련/BOJ

BOJ)5582 공통 부분 문자열

JASON 자손9319 2017. 2. 8. 01:32

문제: icpc.me/5582


두 문자열이 주어질 때 공통 부분 문자열의 최대 길이를 출력하는 문제이다.


두 문자열 사이에 나올 수 없는 한 문자열을 더미로 끼운 뒤 두 문자열을 연결하여 (ex ABC!BCD)


Suffix Array를 이용하여 LCP Array를 구할 때 비교 되는 접미사 SA[i]와 SA[i-1]가 서로 다른 문자열로부터 파생된 것들 중 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
58
59
60
61
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 10000
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] = 'Z' + 1;
    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)) {
            ans = max(ans, LCP[i]);
        }
    }
    printf("%d\n", ans);
    return 0;
}
cs


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

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
BOJ)1893 시저 암호  (0) 2017.02.06
댓글
댓글쓰기 폼