티스토리 뷰

알고리즘 관련/BOJ

BOJ)1701 Cubeditor

JASON 자손9319 2017. 2. 1. 23:46

문제: icpc.me/1701


문자열이 주어질 때 2번이상 나오는 부분 문자열 중 가장 길이가 긴 부분 문자열의 길이를 출력하는 문제이다.


N이 5000밖에 안되기 때문에 문자열의 모든 Suffix에 대해서 failure function을 구해준 뒤 그 중 최댓값을 출력하면 된다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 5001
using namespace std;
char a[MAX_N][MAX_N];
int l, r;
vector<int> pi;
void getpi(const char *c,int len) {
    pi.clear();
    pi.resize(len);
    int j = 0;
    for (int i = 1; i < len; i++) {
        while (j > && c[i] != c[j])
            j = pi[j - 1];
        if (c[i] == c[j])
            pi[i] = ++j;
    }
}
int main() {
    scanf("%s"&a[0]);
    for (int i = 0; i < MAX_N; i++) {
        if (a[0][i] == '\0') {
            l = i;
            break;
        }
    }
    for (int i = 1; i < l; i++) {
        for (int j = 0; j < l - i; j++) {
            a[i][j] = a[i - 1][j + 1];
        }
    }
    for (int i = 0; i < l; i++) {
        getpi(a[i], l - i);
        for (int j : pi)
            r = max(r, j);
    }
    printf("%d\n", r);
    return 0;
}
cs


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

BOJ)2662 기업투자  (0) 2017.02.03
BOJ)9252 LCS 2  (0) 2017.02.02
BOJ)1701 Cubeditor  (0) 2017.02.01
BOJ)11585 속타는 저녁 메뉴  (0) 2017.02.01
BOJ)4354 문자열 제곱  (0) 2017.02.01
BOJ)2233 사과나무  (0) 2017.02.01
TAG
댓글
댓글쓰기 폼