字典树。
代码如下:
#include<iostream> #include<cstdio> #include<string> #include<cstring> using namespace std; struct Trie { char str[15]; Trie *next[26]; }*root; void buildTrie(char *eng,char *mar) { int rt,i,len=strlen(mar); Trie *p=root,*q; for(i=0;i<len;i++){ rt=mar[i]-'a'; if(p->next[rt]==NULL){ q= new Trie; for(int j=0;j<26;j++){ q->next[j]=NULL; q->str[0]='\0'; } p->next[rt]=q; p=p->next[rt]; } else p=p->next[rt]; } strcpy(p->str,eng); } string findTrie(string mar) { int i,len=mar.length(); Trie *q=root; if(len==0) return mar; for(i=0;i<len;i++){ int rt=mar[i]-'a'; if(q->next[rt]==NULL) break; else q=q->next[rt]; } if(len==i&&q->str[0]!='\0') return q->str; else return mar; } void del(Trie *root) { for(int i=0;i<26;i++){ if(root->next[i]!=NULL) del(root->next[i]); } delete root; } int main() { root=new Trie; for(int i=0;i<26;i++) root->next[i]=NULL; char dir[10],eng[11],mar[11]; cin>>dir; string word=""; string ans=""; while(scanf("%s",eng)&&eng[0]!='E'){ scanf("%s",mar); buildTrie(eng,mar); } cin>>dir; getchar(); char str1[3005]; while(gets(str1)&&str1[0]!='E'){ int len=strlen(str1); ans=""; for(int i=0;i<len;i++){ if(str1[i]>='a'&&str1[i]<='z') word+=str1[i]; else{ ans+=findTrie(word); word=""; ans+=str1[i]; } } cout<<ans<<endl; } del(root); return 0; }