hdu1305 字典树水题

题意:

     给你一些字符串,然后问你他们中有没有一个串是另一个串的前缀。

思路:

      字典树水题,(这种水题如果数据不大(这个题目不知道大不大,题目没说估计不大),hash下也行,把每个串拆成len个串,然后map容器记录下就行了,不想存也

行,最后迭代一下也能出来),回来说字典树,就是最简单的前缀判断应用,我写的结构体里面有3个量,next[], v(出现次数) ,mk (是不是某个字符串的最后一位),

在查找的时候如果我们碰到了已经mk的,那么就直接发现前缀了,某个字符串是当前串的前缀,还有一种情况就是没有发现mk但是当前串的最后一位出现的次数大于0,也算

是发现前缀,当前串为某个字符串的前缀。ok就这些。  


#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct
Tree
{

Tree *next[2];
int
v ,mk;
}
Tree; Tree root; void Buid_Tree(char *str)
{
int
len = strlen(str);
Tree *p = &root ,*q;
for(int
i = 0 ;i < len ;i ++)
{
int
id = str[i] - '0';
if(
p -> next[id] == NULL)
{

q = (Tree *)malloc(sizeof(root));
q -> v = 1;
q -> mk = 0;
for(int
j = 0 ;j < 2 ;j ++)
q -> next[j] = NULL;
p -> next[id] = q;
p = p -> next[id];
}
else
{

p = p -> next[id];
p -> v ++;
}
}

p -> mk = 1;
} int
Find(char *str)
{
int
len = strlen(str);
Tree *p = &root;
for(int
i = 0 ;i < len ;i ++)
{
int
id = str[i] - '0';
p = p -> next[id];
if(
p == NULL) return 0;
if(
p -> mk == 1) return 2; }
return
p -> v;
} int main ()
{
char
str[10000];
int
cas = 1;
while(~
scanf("%s" ,str))
{
if(!
strcmp(str ,"9"))
{

printf("Set %d is immediately decodable\n" ,cas ++);
continue;
}

root.next[0] = root.next[1] = NULL;
Buid_Tree(str);
int
mk = 0;
while(
scanf("%s" ,str) && strcmp(str ,"9"))
{
if(
Find(str) > 0) mk = 1;
Buid_Tree(str);
}
if(!
mk) printf("Set %d is immediately decodable\n" ,cas ++);
else
printf("Set %d is not immediately decodable\n" ,cas ++);
}
return
0;
}




上一篇:hdu1305Immediate Decodability(字典树)


下一篇:poj 1056 IMMEDIATE DECODABILITY 字典树