2011-2012 Waterloo Local Contest, 19 June, 2011 D : Compound Words
問題概要
辞書が与えられる。辞書内の文字のうち、辞書内のふたつの言葉が連結されてできたものを全て出力する問題。
解法
文字列の長さが短いので、どこで区切るかを各文字について全探索する。
acceptされたコード
#include <string> #include <cstdio> #include <set> using namespace std; char buf[100]; set<string> all; void init(){ for(;scanf("%[^\n]%*c", buf)!=EOF;all.insert(string(buf))); } void solve(){ for(set<string>::iterator itr=all.begin(); itr!=all.end(); itr++){ string str = *itr; const int L = str.length(); for(int i=1; i<L-1; i++){ if(all.find(str.substr(0, i))!=all.end() && all.find(str.substr(i))!=all.end()){ puts(str.c_str()); break; } } } } int main(){ init(); solve(); return 0; }