[백준] 11656번 : 접미사 배열 (C++)

11656번 : 접미사 배열

---

문제 )

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

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

문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.

 

 

 

출력 :

첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

 

 

 

 

풀이)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(){
    // 입력을 받을 string
    string word;
    // 정렬을 위해 vector를 만들어 단어들을 담는다
    vector<string> words;
 
    cin >> word;
 
    // 입력받은 word를 substr을 이용해 잘라 words에 넣어준다
    for (int i = 0; i < word.length(); i++) {
        words.push_back(word.substr(i, word.length() - i));
    }
 
    // algorithm STL의 sort를 이용하여 정렬한다.
    // 만약 사전 역순으로 정렬해야 한다면, 
    // compare 함수를 따로 구현하여 우선순위를 정해주도록 한다.
    sort(words.begin(), words.end());
 
    // for-each문을 이요하여 words에 담긴 단어들을 출력한다.
    for (auto& ele : words) {
        cout << ele << endl;
    }
 
    return 0;
}

---

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

11656번: 접미사 배열