Hdoj 1247

原题链接

描述

A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
You are to find all the hat’s words in a dictionary.

输入

Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
Only one case.

输出

Your output should contain all the hat’s words, one per line, in alphabetical order.

样例输入

a
ahat
hat
hatword
hziee
word

样例输出

ahat
hatword

思路

字典树。
其他方法需要注意以下情况：
ab
abab
这种情况abab应当输出。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

map<string, int> trie;

int main()
{
    string st1[50002]; int num = 0;
	while(cin >> st1[num])
		trie[st1[num++]] = 1;
	for(int i = 0; i < num; i++)
	{
		int len = st1[i].size();
		string st2 = "";
		int f = 0;
		for(int j = 0; j < len - 1; j++)
		{
			st2 += st1[i][j];
			if(trie[st2])
			{
				string st3 = "";
				for(int k = j + 1; k < len; k++)
				{
					st3 += st1[i][k];
				}
				if(trie[st3]) f = 1;
			}
			if(f) break;
		}
		if(f) cout << st1[i] << endl;
	}
    return 0;
}