글 읽기 - 9248번 문제 질문입니다.

vel1024 3년 전 0

9248 번 Suffix Array 문제를 풀기위해서

아래와 같이 코드를 작성해서 제출 했습니다.

예제로 제시된 abracadabra 의 결과는 제대로 나오는데

채점을 하는 도중에 런타임 에러가 발생합니다.

왜 런타임 에러가 발생하는지

알려주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>

#define MAX_N 500001

using namespace std;

string str;
int t, n, g[MAX_N], tg[MAX_N], RANK[MAX_N], SA[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];
}

void getSA(string str)
{
    t = 1;
    n = str.size();

    for (int i = 0; i < n; i++)
    {
        SA[i] = i;
        g[i] = str[i] - 'a';
    }

    while (t <= n)
    {
        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; 
    }
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    cin >> str;
    getSA(str);

    for (int i = 0; i < n; i++)
    {
        RANK[SA[i]] = i;
    }

    int len = 0;

    for (int i = 0; i < n; i++)
    {
        int k = RANK[i];
        if (k)
        {
            int j = SA[k - 1];

            while (str[j + len] == str[i + len])
                len++;
            LCP[k] = len;

            if (len)
                len--;
        }
    }

    for (int i = 0; i < n; i++)
    {
        cout << SA[i] + 1 << " ";
    }
    cout << '\n';
    for (int i = 0; i < n; i++)
    {
        if (!i)
            cout << "x ";
        else
            cout << LCP[i] << " ";
    }
    return 0;
}

shg9411 3년 전 0

아마 cmp 함수 내에서 x+t, y+t에 문제가 있지 않을까 싶네요.

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

문제

문제

출처

ICPC

9248번 문제 질문입니다.

vel1024 3년 전 0

shg9411 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말