POJ2503：Babelfish

浅谈\(Trie\)：https://www.cnblogs.com/AKMer/p/10444829.html

题目传送门：http://poj.org/problem?id=2503

\(Trie\)树模板题，就是要你实现一个字典查找的功能。读入十分的恶心。

时间复杂度：\(O(len*n)\)

空间复杂度：\(O(len)\)

代码如下：

#include <cstdio>
#include <cstring>
using namespace std;const int maxn=1e5+5;char s[maxn<<1],s1[maxn],s2[maxn];struct Trie {
int tot;
char s[maxn*10][15];
int son[maxn*10][26];void ins() {
int pos=1,len=strlen(s2+1);
for(int i=1;i<=len;i++) {
if(son[pos][s2[i]-'a'])pos=son[pos][s2[i]-'a'];
else pos=son[pos][s2[i]-'a']=++tot;
}
len=strlen(s1+1);
for(int i=1;i<=len;i++)
s[pos][i]=s1[i];
}void find() {
int pos=1,len=strlen(s1+1);
for(int i=1;i<=len;i++) {
if(son[pos][s1[i]-'a'])pos=son[pos][s1[i]-'a'];
else {puts("eh");return;}
}
if(!strlen(s[pos]+1))puts("eh");
else printf("%s\n",s[pos]+1);
}
}T;int main() {
T.tot=1;
while(1) {
int n,pos;
scanf("%[^\n]",s+1);getchar();
if((n=strlen(s+1))==0)break;
for(int i=1;i<=n;i++)
if(s[i]==' ') {pos=i;break;}
for(int i=1;i<pos;i++)s1[i]=s[i];
for(int i=pos+1;i<=n;i++)s2[i-pos]=s[i];
T.ins(),memset(s,0,(n+1)*4);
}
while(~scanf("%s",s1+1))T.find();
return 0;
}