글 읽기 - 안녕하세요 접미사 배열2를 풀다가 궁금증이 생겨 이렇게 글을 적습니다.

sm970124 3년 전 0

안녕하세요 접미사 배열 코드를 적다가 궁금증이 생겨서 이렇게 글을 적습니다. 단순하게

int sa[100001],group[100001], temp_group[100001], t,len;

int group[100001], temp_group[100001], sa[100001],t,len;

변수 선언 순서만 바꾸었는대 하나는 런타임에러가 뜨고 하나는 통과가 됩니다.

뭐가 문제일까요 ㅠㅠ

각각 체점번호 22125026(정답), 22125025(런타임 에러) 입니다

//되는 경우
#include<stdio.h>
int sa[100001],group[100001], temp_group[100001], t,len;
char s[100001];
void quick(int l, int r)
{
	int i, j, m;
	if (l < r)
	{
		i = l - 1;
		j = r + 1;
		m = sa[(l + r) / 2];
		while (1)
		{
			while (group[sa[++i]] == group[m] && group[sa[i] + t] < group[m + t] || group[sa[i]] != group[m] && group[sa[i]]<group[m]);
			while (group[sa[--j]] == group[m] && group[sa[j] + t] > group[m + t] || group[sa[j]] != group[m] && group[sa[j]]>group[m]);
			if (i >= j)break;
			int temp = sa[i];
			sa[i] = sa[j];
			sa[j] = temp;
		}
		quick(l, i - 1);
		quick(j + 1, r);
	}
}
bool cmp(int i, int j)
{
	if (group[i] == group[j])return group[i + t] < group[j + t];
	return group[i] < group[j];
}
void getSA()
{
	while (s[len] != NULL)len++;
	for (int i = 0; i < len; i++)
	{
		group[i] = s[i];//group은 t=1 즉 한글자를 기준으로 그릅화됨
		sa[i] = i;//접미사 배열은 정렬되지 않은 상태
	}
	t = 1;
	while (t <= len)
	{
		group[len] = -1;
		quick(0, len - 1);
		temp_group[sa[0]] = 0;
		for (int i = 1; i < len; i++)
		{
			if (cmp(sa[i - 1], sa[i]))temp_group[sa[i]] = temp_group[sa[i-1]] + 1;
			else temp_group[sa[i]] = temp_group[sa[i - 1]];
		}
		for (int i = 0; i < len; i++)
		{
			  group[i] = temp_group[i];
		}
		t *= 2;
	}
}
int main()
{
	scanf("%s", s);
	getSA();
	for (int i = 0; i < len; i++)printf("%d\n", sa[i]);
}
//안되는 경우
#include<stdio.h>
int group[100001], temp_group[100001], sa[100001],t,len;
char s[100001];
void quick(int l, int r)
{
	int i, j, m;
	if (l < r)
	{
		i = l - 1;
		j = r + 1;
		m = sa[(l + r) / 2];
		while (1)
		{
			while (group[sa[++i]] == group[m] && group[sa[i] + t] < group[m + t] || group[sa[i]] != group[m] && group[sa[i]]<group[m]);
			while (group[sa[--j]] == group[m] && group[sa[j] + t] > group[m + t] || group[sa[j]] != group[m] && group[sa[j]]>group[m]);
			if (i >= j)break;
			int temp = sa[i];
			sa[i] = sa[j];
			sa[j] = temp;
		}
		quick(l, i - 1);
		quick(j + 1, r);
	}
}
bool cmp(int i, int j)
{
	if (group[i] == group[j])return group[i + t] < group[j + t];
	return group[i] < group[j];
}
void getSA()
{
	while (s[len] != NULL)len++;
	for (int i = 0; i < len; i++)
	{
		group[i] = s[i];//group은 t=1 즉 한글자를 기준으로 그릅화됨
		sa[i] = i;//접미사 배열은 정렬되지 않은 상태
	}
	t = 1;
	while (t <= len)
	{
		group[len] = -1;
		quick(0, len - 1);
		temp_group[sa[0]] = 0;
		for (int i = 1; i < len; i++)
		{
			if (cmp(sa[i - 1], sa[i]))temp_group[sa[i]] = temp_group[sa[i-1]] + 1;
			else temp_group[sa[i]] = temp_group[sa[i - 1]];
		}
		for (int i = 0; i < len; i++)
		{
			  group[i] = temp_group[i];
		}
		t *= 2;
	}
}
int main()
{
	scanf("%s", s);
	getSA();
	for (int i = 0; i < len; i++)printf("%d\n", sa[i]);
}

Green55 3년 전 1

undefined behavior가 포함되어 있는지 확인해보세요. 특히, 배열 범위를 벗어난 접근이 있을 확률이 커보입니다.

https://www.secmem.org/blog/2020/01/17/c-c++-and-ub/

sm970124 3년 전 0

말씀하신대로 배열의 크기를 넘어 갈 경우 n으로 값을 고정시켜주니까 런타임 에러는 사라졌습니다. 감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

안녕하세요 접미사 배열2를 풀다가 궁금증이 생겨 이렇게 글을 적습니다.

sm970124 3년 전 0

Green55 3년 전 1

sm970124 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말