题目:给定一个单词本，要求找出其中的单词，是单词本中某两个单词合并起来得。
思路。先把单词本用字典树保存，然后枚举没个单词的切点，把一个单词分成两部分，去字典树中找即可。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn=1e5; const int N=26;//26个小写字母 struct node { int flag;//标记以这个字母结尾为一个单词 int count;//标记以这个字母结尾为一个前缀 struct node *pNext[N];//26枚字符指针 }tree[maxn*N];//大小通常设为 单词个数*单词长度 int t;//表明现在用到了那个节点 struct node *create () { //需要新开一个字符节点，就是有abc这样，插入abd，则d需要新开节点 struct node *p=&tree[t++]; p->flag=0; //初始值为0，不是整个单词 p->count=1; //前缀是必须的，本身就是一个了 for (int i=0;i<N;i++) { p->pNext[i]=NULL;//初始化指针 } return p; } void insert (struct node **T,const char str[]) { struct node *p=*T; if (!p)//空树 { p=*T=create(); } int lenstr=strlen(str+1); for (int i=1;i<=lenstr;i++) //把单词拆开放进树 { int id=str[i]-'a'; //压缩下标 if (p->pNext[id]) //存在过，则前缀++ { p->pNext[id]->count++; //p->pNext[id]表明是id这个字母 } else { p->pNext[id]=create(); } p=p->pNext[id]; } p->flag=1; //表明这字母为结尾是一个单词，上一次已经是p=p->pNext[id]了 //就是现在已经去到了单词的最后一个字母的那个节点了！！ return ; } int find (struct node *T,const char str[]) { struct node *p = T; if (!p) //空树 { return 0; } int lenstr=strlen(str+1); for (int i=1;i<=lenstr;i++) { int id=str[i]-'a'; if (!p->pNext[id]) { return 0; //单词中断，找不到 } p=p->pNext[id]; } return p->flag; //看看是不是一个单词的结尾 } string str[120000+20]; void work () { struct node * T = NULL; int n=1; while (scanf("%s",str[n].c_str()+1) != EOF ) { insert(&T,str[n].c_str()); ++n; } for (int i=1;i<=n-1;++i) { //printf ("%s ",str[i].c_str()+1); int len = 1; while (str[i][len] != ' ') ++len; --len; // printf ("%d ",len); for (int j=1;j<=len-1;++j) { string a,b; a+="0"; b+="0"; for (int k=1;k<=j;++k) a += str[i][k]; for (int k=j+1;k<=len;++k) b += str[i][k]; //cout<<a<<" "<<b<<"***"<<endl; if (find(T,a.c_str())&&find(T,b.c_str())) { printf ("%s ",str[i].c_str()+1); break; } } } return ; } int main() { #ifdef local freopen("data.txt","r",stdin); #endif work(); return 0; }