[BOJ/C++] 접미사 배열(11656번)

1. 개요

https://www.acmicpc.net/problem/11656

11656번: 접미사 배열

1-1. 설명

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해놓은 배열이다. 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 후 출력하는 프로그램을 작성한다.

1-2. 제한 사항

 - 첫 줄에 문자열 S가 주어지며, S는 소문자로 이루어져 있고 길이는 1,000 이하

---

2. 구현

2-1. 풀이

S를 받아 반복문을 통해  substr을 거쳐 접미사 배열을 생성해주었다. 후에 sort 함수를 통해 정렬 후 출력해주었다. 

2-2. 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

constexpr size_t MAX_NUM = 1000;
string strs[MAX_NUM];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string str;
    cin >> str;

    for (int i = 0; i < str.size(); i++) {
        strs[i] = str.substr(i, str.size() - i);
    }

    sort(strs, strs + str.size());

    for (int i = 0; i < str.size(); i++) {
        cout << strs[i] << "\n";
    }

    return 0;
}