Codeforces 988B - Substrings Sort
題意:
給你一些字串,問你這些字串能否重新排列成,所以前面的字串都是此字串的子字串。
思路:
記錄下每個字串有幾個子字串,依照這個數字從小排到大,然後檢查是否每個字串的子字串數量都大於等於目前前面的字串數量,是的話就OK,否則輸出NO。
程式碼:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <algorithm> | |
using namespace std; | |
struct Str | |
{ | |
string s; | |
int n; | |
}; | |
bool is_substring(string a, string b) | |
{ | |
if(a.find(b) != string::npos) | |
{ | |
return true; | |
} | |
return false; | |
} | |
bool comp(Str a, Str b) | |
{ | |
return a.n < b.n; | |
} | |
int main() | |
{ | |
int N; | |
Str S[100]; | |
cin >> N; | |
for(int i = 0; i < N; ++i) | |
{ | |
cin >> S[i].s; | |
S[i].n = 0; | |
} | |
for(int i = 0; i < N; ++i) | |
{ | |
for(int j = 0; j < N; ++j) | |
{ | |
if(i != j && is_substring(S[i].s, S[j].s)) | |
{ | |
++S[i].n; | |
} | |
} | |
} | |
sort(S, S + N, comp); | |
bool ans = true; | |
for(int i = 0; i < N; ++i) | |
{ | |
if(S[i].n < i) | |
{ | |
ans = false; | |
break; | |
} | |
} | |
if(ans) | |
{ | |
cout << "YES" << endl; | |
for(int i = 0; i < N; ++i) | |
{ | |
cout << S[i].s << endl; | |
} | |
} | |
else | |
{ | |
cout << "NO" << endl; | |
} | |
return 0; | |
} |