본문 바로가기
Algorithms/simulation

1256 K번째 접미어

by OKOK 2018. 10. 31.

영어 소문자 문자열 길이가 엔 일 때 접미어들은 문자열의 길이만큼 존재함

몬스터 문자열 아래 그림 왼쪽 접미어 사전적 정렬 아래 그림과 같이 정렬됨

 

몬스터 문자열의 접미어들 중 사전적 순서 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

댓글