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

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

문제

• 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.

• baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.

조건

• 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.
• 첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

풀이

앞에서부터 한글자씩 빼서 저장한 뒤, 사전순으로 정렬을하면 되는 문제이다. 단어를 앞에서부터 한글자씩 빼서 저장하는 방법은 여러가지가 있겠지만, 나는 substr로 구현을 해주었다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

vector<string> sufix;

int main()
{
  fastio;
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++)
  {
    sufix.push_back(s.substr(i, s.size()));
  }
  sort(sufix.begin(), sufix.end());
  for (int i = 0; i < sufix.size(); i++)
  {
    cout << sufix[i] << '\n';
  }
  return 0;
}