[UVA10282] Babelfish

2017年9月12日

你有一本字典,让你把一种语言的单词翻译成另外一种语言的单词。
就是裸的字典树题目。

#include <bits/stdc++.h>
using namespace std;
struct Trie {
  Trie * next[30];
  string word;
  int ok;
  Trie() {
    ok = 0;
    memset(next, 0, sizeof(next));
  }
};
Trie * head;
void insert(string w, string s)
{
  Trie * p = head;
  for (int i = 0; i < s.size(); i++) {
    int c = s[i] - 'a';
    if (p->next[c] == NULL) {
      p->next[c] = new Trie();
    }
    p = p->next[c];
  }
  p->ok = 1;
  p->word = w;
}
void search(string s)
{
  Trie * p = head;
  for (int i = 0; i < s.size(); i++) {
    int c = s[i] - 'a';
    if (p->next[c] == NULL) {
      cout << "eh" << endl;
      return;
    }
    p = p->next[c];
  }
  if (p->ok) 
    cout << p->word << endl;
  else
    cout << "eh" << endl;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  head = new Trie();
  string str;
  while (getline(cin, str)) {
    stringstream ss(str);
    int cnt = 0;
    string tmp[5];
    while (ss >> tmp[cnt]) {
      cnt++;
    }
    if (tmp[0] == "")
      continue;
    if (cnt == 2) {
      insert(tmp[0], tmp[1]);
    } else {
      search(tmp[0]);
    }
  }
  return 0;
}
打赏 赞(0)
微信
支付宝
微信二维码图片

微信扫描二维码打赏

支付宝二维码图片

支付宝扫描二维码打赏

2 thoughts on “[UVA10282] Babelfish

  1. 头像Juventus fotbollströja

    Just wish to say your article is as amazing. The clearness for your submit is just excellent and i could think you’re an expert in this subject. Well with your permission let me to grab your feed to keep updated with imminent post. Thanks one million and please keep up the gratifying work.

    Reply
  2. 头像maglia manchester united fellaini

    Hello there, simply become aware of your weblog thru Google, and found that it is truly informative. I am gonna be careful for brussels. I’ll appreciate should you proceed this in future. Many other folks can be benefited out of your writing. Cheers!

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注