E - What Are You Talking About
Ignatius is so lucky that he met a Martian yesterday. But he didn't know the language the Martians use. The Martian gives him a history book of Mars and a dictionary when it leaves. Now Ignatius want to translate the history book into English. Can you help him?
InputThe problem has only one test case, the test case consists of two parts, the dictionary part and the book part. The dictionary part starts with a single line contains a string "START", this string should be ignored, then some lines follow, each line contains two strings, the first one is a word in English, the second one is the corresponding word in Martian's language. A line with a single string "END" indicates the end of the directory part, and this string should be ignored. The book part starts with a single line contains a string "START", this string should be ignored, then an article written in Martian's language. You should translate the article into English with the dictionary. If you find the word in the dictionary you should translate it and write the new word into your translation, if you can't find the word in the dictionary you do not have to translate it, and just copy the old word to your translation. Space(' '), tab(' '), enter(' ') and all the punctuation should not be translated. A line with a single string "END" indicates the end of the book part, and that's also the end of the input. All the words are in the lowercase, and each word will contain at most 10 characters, and each line will contain at most 3000 characters.
OutputIn this problem, you have to output the translation of the history book.
Sample Input
START
from fiwo
hello difh
mars riwosf
earth fnnvk
like fiiwj
END
START
difh, i'm fiwo riwosf.
i fiiwj fnnvk!
END
Sample Output
hello, i'm from mars.
i like earth!
Hint
Huge input, scanf is recommended.
一开始我我卡在输入上面start end 还考虑了分割空格 。 一开始的想法是用结构体将英语和火星文联系起来。。
发现字典树中结构体根本发挥不出我想要的作用。后来还是借鉴了网上ac码。。
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
int tree[500000][26] = {0} ; // 一开始定义400000没想到runtime errror了
int color[500000] = {0};
int k = 0 , ans = 0 ;
char str[500000] , str1[50000] , str2[50000], estr[500000][20];
void winsert(char *s , char *s1) // 将火星文插入字典树中
{
int p = 0 ;
for(int i = 0 ; i < strlen(s) ; i++)
{
int c = s[i] - '0';
if(!tree[p][c]) tree[p][c] = ++k ;
p = tree[p][c];
}
color[p] = 1 ;
// 巧妙的将火星文和英语联系起来
strcpy(estr[p] , s1); // 开一个新将英文存入该火星文的末编号里
}
void wsearch(char * s)
{
int p = 0 ;
for(int i = 0 ; i < strlen(s) ; i++)
{
int c = s[i] - '0' ;
if(!tree[p][c])//如果该字典无该火星单词的翻译则原样输出并返回
{
printf("%s" , s);
return ;
}
p = tree[p][c];
}
if(color[p] == 1) // 如果该火星单词存在翻译
{
printf("%s" , estr[p]); // 输出翻译
}
else
{
printf("%s" , s); // 原文输出
}
}
int main()
{
// 这个题的输入让我头疼
scanf("%s" , str);
while(scanf("%s" , str))
{
if(strcmp(str , "END")== 0) // 判断是否为end结束
break ;
scanf("%s" , str1);
winsert(str1 , str);
}
scanf("%s" , str);
getchar() ; // 吸收回车
while(gets(str) && strcmp(str , "END") != 0) // 整行输入并判断end
{
int len = strlen(str);
ans = 0 ;
for(int i = 0 ; i < len ; i++) // 遍历这句话
{
if(islower(str[i])) // 判断是否为小写字母
{
str2[ans++] = str[i]; // 用一个数组存一串小写字母
}
else//如果不为小写字母
{
str2[ans] = 0 ;
wsearch(str2); // 查找该串小写字母
ans = 0 ;//更新小写字母数组
printf("%c" , str[i]);//打印不为小写字母字符
}
}
cout << endl ;
}
return 0;
}
H - 全文检索
我们大家经常用google检索信息，但是检索信息的程序是很困难编写的；现在请你编写一个简单的全文检索程序。
问题的描述是这样的：给定一个信息流文件，信息完全有数字组成，数字个数不超过60000个，但也不少于60个；再给定一个关键字集合，其中关键字个数不超过10000个，每个关键字的信息数字不超过60个，但也不少于5个；两个不同的关键字的前4个数字是不相同的；由于流文件太长，已经把它分成多行；请你编写一个程序检索出有那些关键字在文件中出现过。
问题的描述是这样的：给定一个信息流文件，信息完全有数字组成，数字个数不超过60000个，但也不少于60个；再给定一个关键字集合，其中关键字个数不超过10000个，每个关键字的信息数字不超过60个，但也不少于5个；两个不同的关键字的前4个数字是不相同的；由于流文件太长，已经把它分成多行；请你编写一个程序检索出有那些关键字在文件中出现过。
Input第一行是两个整数M，N；M表示数字信息的行数，N表示关键字的个数；接着是M行信息数字，然后是一个空行；再接着是N行关键字；每个关键字的形式是：[Key No. 1] 84336606737854833158。
Output输出只有一行，如果检索到有关键字出现，则依次输出，但不能重复，中间有空格，形式如：Found key: [Key No. 9] [Key No. 5]；如果没找到，则输出形如：No key can be found !。
Sample Input
20 10
646371829920732613433350295911348731863560763634906583816269
637943246892596447991938395877747771811648872332524287543417
420073458038799863383943942530626367011418831418830378814827
679789991249141417051280978492595526784382732523080941390128
848936060512743730770176538411912533308591624872304820548423
057714962038959390276719431970894771269272915078424294911604
285668850536322870175463184619212279227080486085232196545993
274120348544992476883699966392847818898765000210113407285843
826588950728649155284642040381621412034311030525211673826615
398392584951483398200573382259746978916038978673319211750951
759887080899375947416778162964542298155439321112519055818097
642777682095251801728347934613082147096788006630252328830397
651057159088107635467760822355648170303701893489665828841446
069075452303785944262412169703756833446978261465128188378490
310770144518810438159567647733036073099159346768788307780542
503526691711872185060586699672220882332373316019934540754940
773329948050821544112511169610221737386427076709247489217919
035158663949436676762790541915664544880091332011868983231199
331629190771638894322709719381139120258155869538381417179544
000361739177065479939154438487026200359760114591903421347697
[Key No. 1] 934134543994403697353070375063
[Key No. 2] 261985859328131064098820791211
[Key No. 3] 306654944587896551585198958148
[Key No. 4] 338705582224622197932744664740
[Key No. 5] 619212279227080486085232196545
[Key No. 6] 333721611669515948347341113196
[Key No. 7] 558413268297940936497001402385
[Key No. 8] 212078302886403292548019629313
[Key No. 9] 877747771811648872332524287543
[Key No. 10] 488616113330539801137218227609
Sample Output
Found key: [Key No. 9] [Key No. 5]
这道题卡在关键信息的输入和关键信息的长度与原文匹配上
一开始我想将关键字插入字典树。。将数字流串联。。然后遍历数字流
再遍历关键信息取关键信息长度并取对应长度的数字流进行查找，，发现出现各种问题，，序号找不到，重复输出等等。。
还是参考了网上ac码
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
int tree[600000][26] = {0} ;
int color[600000] = {0};
int k = 0 , ans = 0 ;
//int flag = 0 ;
char str[60000] , str1[60000] , str2[60000], estr[600000][20];
void winsert(char *s , int i)
{
int p = 0 ;
for(int i = 0 ; s[i] ; i++) // 当输入很多时strlen取长度会超时
{
int c = s[i] - '0' ;
if(!tree[p][c]) tree[p][c] = ++k;
p = tree[p][c] ;
}
color[p] = i ; // 巧妙的用序号作为末标记
}
void wsearch(char *s)
{
int p = 0 ;
for(int i = 0 ; s[i] ; i++)
{
int c = s[i] - '0' ;
if(color[p]) // 如果匹配到关键信息
{
if(flag == 0)
cout << "Found key:" ;
cout << " [Key No. " << color[p] << "]" ; // 输出
// color[p] = 0 ; // 避免重复索引到并输出
// flag = 1 ;
}
if(!tree[p][c]) return ;//没找到就返回
p = tree[p][c] ;
}
}
int main()
{
int m , n ;
scanf("%d%d" , &m, &n);
int ans = 0 ;
for(int i = 0 ; i < m ; i++)
{
scanf("%s" , str);
for(int j = 0 ; j < strlen(str) ; j++) // 将数字流串联起来
str1[ans++] = str[j] ;
}
for(int i =1 ; i <= n ; i++)
{
scanf("%s" , str2);//将没有用的输入覆盖 ， 只要输入最后的关键信息
scanf("%s" , str2);
scanf("%s" , str2);
scanf("%s" , str2);
winsert(str2 , i); // 用序号做标记
}
for(int i = 0 ; i < strlen(str1) ; i++)
wsearch(str1 + i); // 更新起始数字流进行查找（好处是不需要考虑关键信息的长度）
/*if(flag == 0)
cout << "NO found " << endl ; */
cout << endl ;
return 0;
}