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.
<mark>Input</mark>
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.
<mark>Output</mark>
Your output should contain all the hat’s words, one per line, in alphabetical order.
<mark>Sample Input</mark>
a
ahat
hat
hatword
hziee
word
<mark>Sample Output</mark>
ahat
hatword

题目大意是说按照字典序给出若干行单词，你需要找出由两个单词组成的单词，并且按照字典序输出，但是坑点就是如果你按照题目给出的单词顺序输出（题目中所谓的字典序输入）是会wa的必须要将其重新排列一下，扫除这个坑点就很好办了，我们的思路是这样，按照单词的输入建立一颗字典树，枚举每个单词的前缀以及后缀，如果发现符合题意那么久把这个单词记录下来最后排序输出， 在暴力枚举每个单词的前缀以及后缀时，有一个非常好用的函数 substr(),

这里介绍一下substr()函数的用法

#include<iostream>
#include<string>

using namespace std;

int main()
{
	string str = "Accepted";
	for(int j = 0; j < str.length(); j++)
	{
		cout << str.substr(0, j + 1) << " " << str.substr(j + 1) << endl;
	}
	return 0;
}

输出结果

A ccepted
Ac cepted
Acc epted
Acce pted
Accep ted
Accept ed
Accepte d
Accepted

这样就可以枚举单词的每一个前缀以及后缀了，subst()中两个参数，分别表示开始和结束的位置；

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

const int MAXN = 5e6 + 5;

int trie[MAXN][29], flag[MAXN], rt, tot = 1;
vector<string> ans;

void Insert_trie(string data)
{
    int len = data.length();
    rt = 0;
    for(register int i = 0; i < len; ++i)
    {
        int y = data[i] - 'a';
        if(trie[rt][y] == 0)
        {
            flag[tot] = 0;
            trie[rt][y] = tot++;
        }
        rt = trie[rt][y];

    }
    flag[rt] = 1;
    //cout << "*************" << endl << rt << endl << "***********" << endl;
}

bool Query_trie(string str)
{
    int len = str.length();
    rt = 0;
    for(register int j = 0; j < len; ++j)
    {
        int y = str[j] - 'a';

        if(trie[rt][y] == 0)
            return false;
            rt = trie[rt][y];
    }
   // cout << rt << "&&&&&" << flag[rt] << endl;
    //rt = trie[rt][y];
   // cout << flag[rt] << endl;
    return flag[rt];
}

int main()
{
    string word[50001];
    int tt = 0;
    while(cin >> word[tt])
    {
        Insert_trie(word[tt]);
        ++tt;
    }
    for(int i = 0; i < tt; ++i)
    {
       // cout << "--------------" << endl;
        int len = word[i].length();
        for(int j = 0; j < len; ++j)
        {
            //cout << j << endl;
            //cout << word[i].substr(0, j + 1) << " " << word[i].substr(j + 1) << endl;
            //-cout << Query_trie(word[i].substr(0, j + 1)) << " " << Query_trie(word[i].substr(j + 1)) << endl;
            if(Query_trie(word[i].substr(0, j + 1)) && Query_trie(word[i].substr(j + 1)))
            {
                //cout << word[i] << endl;
                ans.push_back(word[i]);
                break;
            }
        }
    }
    sort(ans.begin(), ans.end());
    int t = ans.size();
    for(int i = 0; i < t; i++)
    {
        cout << ans[i] << endl;
    }
    return 0;
}