给定一个词典，要求求出其中所有的复合词，即恰好有两个单词连接而成的词
trie存储以该单词为前缀的单词数量，然后对于每个单词，，看在字典中的以该单词为前缀的单词“减去”原单词剩下的单词是否在字典中，如果是储存这个答案到ans的set中
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> #include<set>#define eps 1e-6 #define LL long long using namespace std; const int maxn = 120000 + 100;const int INF = 0x3f3f3f3f;struct Trie {int ch[maxn][30];int val[maxn];int sz;Trie() {sz = 1; memset(ch[0], 0, sizeof(ch[0]));}int idx(char c) { return c – 'a';}void insert(char *s) {int u = 0, n = strlen(s);for(int i = 0; i < n; i++) {int c = idx(s[i]);if(!ch[u][c]) {memset(ch[sz], 0, sizeof(ch[sz]));val[sz] = 0;ch[u][c] = sz++;}else val[ch[u][c]]++;u = ch[u][c];}}int find(char *s) {int u = 0, n = strlen(s);for(int i = 0; i < n; i++) {int c = idx(s[i]);if(!ch[u][c]) return 0;u = ch[u][c];}return val[u];}} trie;vector<string> dic;set<string> word;set<string> ans;void init() {string tmp;while(cin >> tmp) {dic.push_back(tmp);word.insert(tmp);trie.insert((char *)tmp.c_str());}}void solve() {int sz = dic.size();for(int i = 0; i < sz; i++) {//cout << (char *)dic[i].c_str() << endl;int cnt = trie.find((char *)dic[i].c_str());// cout << cnt << endl;int wsz = dic[i].size();for(int j = 1; j <= cnt; j++) {if(word.count(dic[i+j].substr(wsz, dic[i+j].size()-wsz)))ans.insert(dic[i+j]);}}for(set<string>::iterator it = ans.begin(); it != ans.end(); it++) cout << *it << endl;}int main() {//freopen("input.txt", "r", stdin);init();solve();return 0;}
人生就像一场旅行，不必在乎目的地，
