Codeforces Round #486 (Div. 3) - B. Substrings Sort

https://codeforces.com/contest/988/problem/B

1. 문제

B. Substrings Sort

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given $n$ strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its substrings.

String $a$ is a substring of string $b$ if it is possible to choose several consecutive letters in $b$ in such a way that they form $a$. For example, string "for" is contained as a substring in strings "codeforces", "for" and "therefore", but is not contained as a substring in strings "four", "fofo" and "rof".

2. 알고리즘

문자열을 크기 별로 정렬 한다.

현재 문자가 다음 문자에 포함되어있는지 검사한다.

포함 되어 있지 않으면 NO 를 출력한다.

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
using namespace std;
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; ++i)
        cin >> s[i];
 
    sort(s.begin(), s.end(), [&] (const string &s, const string &t) {
        return s.size() < t.size();
    });
 
    for (int i = 0; i < n - 1; ++i) {
        if (s[i + 1].find(s[i]) == string::npos) {
            cout << "NO\n";
            return 0;
        }
    }
 
    cout << "YES\n";
    for (auto it : s)
        cout << it << endl;
 
    return 0;
}