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;
}