Codeforces #170 Div2 B "New Problem"
問題
文字列がN個与えられる。
これらの文字列のどの部分文字列とも一致しないような
なるべく長さの短い文字列を返せ。
そのような文字列が複数あるのなら、
辞書順で最も小さいものを返せ。
例)
インプット
N = 2
hello world
apple
アウトプット
b
インプット
abcdefghijklmn
opqrstuvwxyz
アウトプット
aa
制約
1 <= 文字列の数 <= 30
1 <= 文字列の長さ <= 20
考えた事
使ってないアルファベットがあればその中で小さいの選べばいいし、
そうじゃなきゃ2文字で調べればいいかな(適当)
SUBMIT後・・・
文字列の長さは多くても30*20の600
長さ2の文字列の種類は26*26の676
ってことは2文字まで調べりゃダイジョブだ。よかったよかった
ソースコード
int main() { istream& in = cin; int n; in >> n; vector<string> v; for( int i = 0; i < n; i++ ){ string str; in >> str; v.push_back(str); } set<char> use; map<char, set<char> > use2; for( int i = 0; i < n; i++ ){ char p, c; for( int j = 0; j < v[i].length(); j++ ){ c = v[i][j]; use.insert(c); if( j != 0 ){ use2[p].insert(c); } p = c; } } // 使ってないアルファベットがあった if( use.size() != 26 ){ for( char ch = 'a'; ch <= 'z'; ch++ ){ if( use.find(ch) == use.end() ){ cout << ch << endl; break; } } }else{ // 2文字の部分文字列で使ってないのを探す bool find = false; for( char c1 = 'a'; c1 <= 'z' && !find; c1++ ){ set<char> s = use2[c1]; for( char c2 = 'a'; c2 <= 'z' && !find; c2++ ){ if( s.find(c2) == s.end() ){ cout << c1 << c2 << endl; find = true; } } } } return 0; }