前面学了Trie,那么就即学即用,运用Trie数据结构来解决这道题目。
本题目比较简单,当然可以不使用Trie,不过多用高级数据结构还是很有好处的。
题目:
Vova is fond of anime. He is so enthusiastic about this art that he learned to communicate with his Japanese friends using their native language. However, for writing email messages Vova has to use
Latin letters. He wants to type hieroglyphs from his keyboard. His team-mate Sergey, in order to help Vova, created an applet that makes it possible to write hieroglyphs by means of typing Latin letters on the keyboard. Each hieroglyph is represented by a
sequence of two Latin letters. This correspondence is given in a special reference book compiled by Sergey. When the applet realizes that a sequence of Latin letters corresponding to a hieroglyph has been typed, it replaces the sequence with this hieroglyph.
When Vova started using Sergey's program, he quickly became bored of looking into the reference book so often. Help Sergey to upgrade the applet in such a way that for each typed Latin letter it would
automatically supply a prompt helping to continue this letter to a sequence representing a hieroglyph.
Input
The first line contains the number of hieroglyphs in Sergey's reference bookN(1≤N≤1000). Each of the nextNlines contains a sequence of two lowercase Latin letters
corresponding to a hieroglyph. The next line contains a lowercase Latin letter entered by Vova.
Output
Output sequences from the reference book that start with the given letter, one sequence per line, in an arbitrary order. If there are no such sequences, then output nothing.
Sample
input
output
6
na
no
ni
ki
ka
ku
k
|
ka
ki
ku
|
本题就是实现一个简单的字典提示功能,可以使用hash表的方法来做,实现起来也很简单。
这里我做了个Trie Class来实现:
#include <iostream>
using namespace std;
#define ALPHA_SIZE 26
#define CHAR_TO_INDEX(c) (c - 'a')
struct HieroglyphsTrie_Node
{
int val;
HieroglyphsTrie_Node *children[ALPHA_SIZE];
};
struct HieroglyphsTrie
{
HieroglyphsTrie_Node *root;
int size;
};
class HieroglyphsTrieClass
{
HieroglyphsTrie *pTrie;
public:
HieroglyphsTrieClass()
{
pTrie = (HieroglyphsTrie *) malloc (sizeof(HieroglyphsTrie));
init();
}
HieroglyphsTrie_Node *getNode()
{
HieroglyphsTrie_Node *pNode = nullptr;
pNode = (HieroglyphsTrie_Node *)malloc(sizeof(HieroglyphsTrie_Node));
if (pNode)
{
pNode->val = 0;
for (int i = 0; i < ALPHA_SIZE; i++)
{
pNode->children[i] = nullptr;
}
}
return pNode;
}
void init()
{
pTrie->root = getNode();
pTrie->size = 0;
}
void insert(const char key[])
{
int len = strlen(key);
int id = 0;
HieroglyphsTrie_Node *pCrawl = pTrie->root;
pTrie->size++;
for (int lv = 0; lv < len; lv++)
{
id = CHAR_TO_INDEX(key[lv]);
if (!pCrawl->children[id])
{
pCrawl->children[id] = getNode();
}
pCrawl = pCrawl->children[id];
}
pCrawl->val = pTrie->size;
}
int search(char key[])
{
int len = strlen(key);
int id = 0;
HieroglyphsTrie_Node *pCrawl = pTrie->root;
for (int lv = 0; lv < len; lv++)
{
id = CHAR_TO_INDEX(key[lv]);
if (!pCrawl->children[id]) return 0;
pCrawl = pCrawl->children[id];
}
return (int)(0 != pCrawl->val);
}
void HieroglyphsRun()
{
int n = 0;
cin>>n;
char ch[3];//不能是ch[2],因为后面还要多一个'\0'终止符
while (n--)
{
cin>>ch;
insert(ch);
}
char k;
cin>>k;
HieroglyphsTrie_Node *pCrawl = nullptr;
pCrawl = pTrie->root->children[CHAR_TO_INDEX(k)];
if (pCrawl)
{
for (int i = 0; i < ALPHA_SIZE; i++)
{
if (pCrawl->children[i])
{
cout<<k<<char('a'+i)<<endl;
}
}
}
}
};
int main()
{
HieroglyphsTrieClass hie;
hie.HieroglyphsRun();
return 0;
}
本类暂时还是不是完善的,慢慢完善吧,不过可以很好完成本题了。
分享到:
相关推荐
acm.timus.ru最全代码
leetcode中国 InterView_Problem English LeetCode / ...刷题代码,主要是java实现,可能会有其他语言代码 代码来自LeetCode / NowCoder / timus 等 site url LeetCode NowCoder Timus LeetCode-cn
acm.timus.ru解决方案 这些是我对ACM.TIMUS.RU问题的解决方案
In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to remember such a kind of numbers. One method to do it in an easy way is to assign ...
timus.ru_solutions 使用的语言:Python 使用的Python版本:3.9 我可以用Python语言解决的一些问题在“ python”目录中。 有些解决方案可以在Java中运行,但确切的解决方案/算法在Python中不起作用! 不知道为什么我...
资源分类:Python库 所属语言:Python 资源全名:timus-sender-0.1.1.post1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
acm.timus.ru 1709 problem
timus.ru_solutions_python 使用的python:3.9 我可以用Python语言解决的一些问题在python目录中。 有些解决方案可以在Java中运行,但确切的解决方案/算法在Python中不起作用! 我不知道为什么
Timus上习题解答与代码参考,这一部分对应于Timus上的Beginner部分的习题
timus:Timus在线法官问题
将图表添加到Timus Online Judge配置文件 该扩展程序将已解决问题的数量图表添加到Timus Online Judge的个人资料和比较器中。 功能:*概要文件和比较中已解决问题计数的图表*向图表中添加更多用户,删除它们,自定义...
https://acm.timus.ru/problem.aspx?space=1&num=1119 题目答案
timus OJ 1197 lonesome kinght
Timus图表 将图表添加到Timus Online Judge个人资料中 特征 概要文件中和比较期间已解决问题的计数图表 向图表添加更多用户,删除它们,自定义图例颜色 缓存配置文件数据 隐藏图表 (可选)突出显示最近两个月内接受...
蒂莫斯 该文件夹包含用Python编写的文件(主要是Python2.7,有些是Python3.4)我通过这些文件在timus上通过了相应的测试。
美国著名在线题库,专门为信息学竞赛选手准备 TJU http://acm.tongji.edu.cn/ 同济大学在线题库,唯一的中文题库,适合NOIP选手 ZJU http://acm.zju.edu.cn/ 浙江大学在线题库 JLU file:///M|/acm/ACM大量习题题库及...
语言:English将图表添加到Timus Online Judge个人资料中该扩展程序将已解决问题的数量图表添加到Timus Online Judge的个人资料和比较器中。功能:*概要文件和比较中已解决问题计数的图表*向图表中添加更多用户,删除...
timus-online-judge Timus Online Judge 是俄罗斯最大的带有自动评判系统的编程问题档案。 问题主要是从在乌拉尔联邦大学、乌拉尔锦标赛、乌拉尔 ACM ICPC 次区域比赛和彼得罗扎沃茨克训练营举办的比赛中收集的。 ...
http://acm.timus.ru/problem.aspx?space=1&num=1362 一道树形动态规划的题目解答,ural1362
Pascal acm_timus_ural_1148.pas