Zoj 1109 Language of FatMouse(文字列_辞書ツリー)
タイトルリンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1109
複数の文字列が与えられ、各列は別の文字列に対応します.いくつかの文字列が与えられ、対応する文字列が出力されます.
解題構想:辞書ツリーで解き、まずツリーを作成し、辞書ツリーノードに保存された情報:出現した文字列の末尾であるかどうか、はい、それに対応する文字列を記録します.各列をクエリーします.
テストデータ:
dog ogday
cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay
コード:
ZeroClockオリジナルですが、私たちは兄弟なので転載できます.
複数の文字列が与えられ、各列は別の文字列に対応します.いくつかの文字列が与えられ、対応する文字列が出力されます.
解題構想:辞書ツリーで解き、まずツリーを作成し、辞書ツリーノードに保存された情報:出現した文字列の末尾であるかどうか、はい、それに対応する文字列を記録します.各列をクエリーします.
テストデータ:
dog ogday
cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay
コード:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 110000
struct node {
char str[11];
node *next[26];
}*root;
char dir[26],fat[26],tar[26];
node *CreateNode() {
node *p;
p = (node *) malloc (sizeof(node));
p->str[0] = '\0';
for (int i = 0; i < 26; ++i)
p->next[i] = NULL;
return p;
}
void Insert(char *fat,char *dir) {
int i = 0,k;
node *p = root;
while (fat[i]) {
k = fat[i++] - 'a';
if (p->next[k] == NULL)
p->next[k] = CreateNode();
p = p->next[k];
}
strcpy(p->str,dir);
}
char *Query(char *str) {
int i = 0,k;
node *p = root;
while (str[i]) {
k = str[i++] - 'a';
if (p->next[k]==NULL)
break;
p = p->next[k];
}
return p->str;
}
int main()
{
int i,j,k;
char c;
root = CreateNode();
while (c = getchar(),c != '
') {
i = 0;
dir[i++] = c;
while (c = getchar(),c != ' ')
dir[i++] = c;
dir[i] = '\0';
i = 0;
while (c = getchar(),c != '
')
fat[i++] = c;
fat[i] = '\0';
Insert(fat,dir);
}
while (scanf("%s",tar) != EOF) {
char *ans = Query(tar);
if (ans[0] == '\0')
printf("eh
");
else printf("%s
",ans);
}
}ZeroClockオリジナルですが、私たちは兄弟なので転載できます.