글 읽기 - 두 코드의 차이를 잘 모르겠습니다.

golazcc83 3년 전 0

suffix sort의 구현 부분은 완전히 똑같지만 입력을 다르게 받았을 뿐인데 맞았고 틀리고가 갈리네요. 입력 2의 경우에는 뒤에 개행 문자나 EOF가 올 수 있다는 가정 하에 저렇게 받았는데 제 머리로는 왜 틀렸는지 도저히 이해가 가지 않습니다 ㅠㅠ

입력 2 부분에 무슨 문제가 있는걸까요?

입력 2와 같은 방식으로 입력을 받은 비슷한 문제는 맞았습니다! 판정을 받았습니다. (채점번호 : 19565908)

#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second

using namespace std;
// i, suffix[i]
typedef pair<int,int> pii;
typedef pair<pii, int> piii;

char S[500002];
int sz;
int dp[500002], suffix[500002], lcp[500002];
piii tmp[500001];

void suffix_sort() {
    for(int i = 0; i < sz; ++i)
        dp[i] = S[i];

    int n = 1;
    while(n <= sz) {
        for(int i = 0; i < sz; ++i) {
            if(i + n < sz)
                tmp[i] = {{dp[i], dp[i + n]}, i};
            else
                tmp[i] = {{dp[i], -1}, i};
        }

        sort(tmp, tmp + sz);

        int idx = 0;
        dp[tmp[0].y] = 0;
        for(int i = 1; i < sz; ++i) {
            if(tmp[i].x.x != tmp[i - 1].x.x || tmp[i].x.y != tmp[i - 1].x.y)
                ++idx;
            dp[tmp[i].y] = idx;
        }
        n <<= 1;
    }

    for(int i = 0; i < sz; ++i)
        suffix[dp[i]] = i;

    int h = 0;
    for(int i = 0; i < sz; ++i) {
        if(dp[i] != 0) {
            int j = suffix[dp[i] - 1];
            while(S[i + h] == S[j + h]) ++h;
            lcp[dp[i]] = h;
        }
        if(h != 0) --h;
    }

    return;
}

int main() {
    // 입력 1 (정답)
    scanf("%s", &S);
    sz = strlen(S);

    // 입력 2 (오답)
    // fgets(S, 500002, stdin);
    // sz = strlen(S) - 1;
    
    suffix_sort();

    for(int i = 0; i < sz; ++i)
        printf("%d ", suffix[i] + 1);
    printf("\nx ");
    for(int i = 1; i < sz; ++i)
        printf("%d ", lcp[i]);
    printf("\n");

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

두 코드의 차이를 잘 모르겠습니다.

golazcc83 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말