영어 소문자 문자열 길이가 엔 일 때 접미어들은 문자열의 길이만큼 존재함
몬스터 문자열 아래 그림 왼쪽 접미어 사전적 정렬 아래 그림과 같이 정렬됨
몬스터 문자열의 접미어들 중 사전적 순서 4번쨰 오는 접미어 onster
K값과 문자열 주어지면 접미어들 중 사전적 순서 K번째 접미어 찾아서 출력
#include <stdio.h>
int main()
{
int T;
char str[1001];
int memory[1001];
int count[27];
int rank[27];
int order[1001];
int vector[1001];
int vectorIndex;
scanf("%d", &T); // 테케 수 받음
for (int tc = 1; tc <= T; tc++)
{
int K;
int ans;
scanf("%d", &K); // 케이를 받음
K;
scanf("%s", str); // 문자열을 받음
for (int i = 0; i < 26; i++)
{
count[i] = 0; // 카운트 초기화
}
int size = 0;
for (size = 0; str[size]; size++) // 가운데 str[size] 이게 뭐지.
{
memory[size] = str[size] - 'a' + 1; // 메모리와
vector[size] = size; // 벡터를 저장
}
memory[size] = 0;
vectorIndex = size;
int shift = 0;
while (vectorIndex > 1)
{
for (int i = 0; i < vectorIndex; i++)
{
count[memory[vector[i] + shift]]++;
}
rank[0] = 0;
int next = 0;
for (int i = 1; i < 27; i++)
{
rank[i] = rank[i - 1] + count[i - 1];
if (rank[i] < K)
{
next = i;
}
}
K -= rank[next];
int nextVectorIndex = 0;
for (int i = 0; i < vectorIndex; i++)
{
order[i] = rank[memory[vector[i] + shift]];
rank[memory[vector[i] + shift]]++;
if (memory[vector[i] + shift] == next)
{
vector[nextVectorIndex] = vector[i];
nextVectorIndex++;
}
}
vectorIndex = nextVectorIndex;
for (int i = 0; i < 27; i++)
{
count[i] = 0;
}
shift++;
}
printf("#%d %s\n", tc, &str[vector[0]]);
}
return 0;
}
'Algorithms > simulation' 카테고리의 다른 글
1265 달란트 (0) | 2018.10.31 |
---|---|
1258 행렬찾기 (0) | 2018.10.31 |
1251 하나로 (0) | 2018.10.31 |
The Exponetial Family / Nonparmetric Methods (0) | 2018.10.28 |
1247 최적 경로 풀이중 (0) | 2018.10.26 |
댓글