HDU1251：http://acm.hdu.edu.cn/showproblem.php?pid=1251
题目大意：求得以该字符串为前缀的数目，注意输入格式就行了。
#include<stdio.h>
#include<string.h> char str[];
int trie[ * ][], cnt;
int sum[ * ]; void insert()
{
int len = strlen(str);
int rt = ;
for(int i = ; i < len; i ++)
{
int id = str[i] - 'a';
if(!trie[rt][id])
trie[rt][id] = ++ cnt;
rt = trie[rt][id];
sum[rt] ++;
}
} int serach()
{
int len = strlen(str);
int rt = ;
for(int i = ; i < len; i ++)
{
int id = str[i] - 'a';
if(!trie[rt][id])
return ;
rt = trie[rt][id];
}
return sum[rt];
} int main()
{
while(gets(str))
{
if(strlen(str) == )
break;
insert();
}
while(scanf("%s", str) != EOF)
{
printf("%d\n", serach());
}
return ;
}
HDU1251
HDU1305：http://acm.hdu.edu.cn/showproblem.php?pid=1305
题目大意：字符串之间互相不为前缀，则输出YES 否则NO
#include<stdio.h>
#include<string.h>
#define mem(a, b) memset(a, b, sizeof(a)) int trie[][], tot, k_rt[], cnt, sum[];
char str[]; void insert()
{
int len = strlen(str);
int root = ;
for(int i = ; i < len; i ++)
{
int id = str[i] - '';
if(!trie[root][id])
trie[root][id] = ++ tot;
root = trie[root][id];
sum[root] ++;
}
k_rt[++ cnt] = root; //记录每个01字符串结束的位置
} void init()
{
mem(trie, );
mem(k_rt, );
mem(sum, );
cnt = , tot = ;
} int main()
{
int k = , flag;
while(scanf("%s", str) != EOF)
{
if(str[] != '')
insert();
else
{
flag = ;
for(int i = ; i <= cnt; i ++)
{
if(sum[k_rt[i]] >= )
{
flag = ;
break;
}
}
if(flag)
printf("Set %d is not immediately decodable\n", k ++);
else
printf("Set %d is immediately decodable\n", k ++);
init();
}
}
return ;
}
HDU1305
HDU1671：http://acm.hdu.edu.cn/showproblem.php?pid=1671
题目大意：与HDU1251是一样的
#include<stdio.h>
#include<string.h>
#define mem(a, b) memset(a, b, sizeof(a)) char str[];
int trie[][], tot, cnt, k_rt[], sum[]; void insert()
{
int len = strlen(str);
int root = ;
for(int i = ; i < len; i ++)
{
int id = str[i] - '';
if(!trie[root][id])
trie[root][id] = ++ tot;
root = trie[root][id];
sum[root] ++;
}
k_rt[++ cnt] = root; //记录每个字符串的结束位置 ，通过结束位置上的出现次数判断是否是其他字符串的前缀
} void init()
{
mem(trie, );
mem(sum, );
mem(k_rt, );
tot = , cnt = ;
} int main()
{
int T, n, flag;
scanf("%d", &T);
while(T --)
{
init();
flag = ;
scanf("%d", &n);
getchar();
for(int i = ; i <= n; i ++)
{
scanf("%s", str);
insert();
}
for(int i = ; i <= cnt; i ++)
{
if(sum[k_rt[i]] >= )
{
flag = ;
break;
}
}
if(flag)
printf("NO\n");
else
printf("YES\n");
}
return ;
}
HDU1671
模板
字典树建树模板：
//建trie树
void insert()
{
int len = strlen(str);
int root = ;
for(int i = ; i < len; i ++)
{
int id = str[i] - '';
if(!trie[root][id])
trie[root][id] = ++ tot;
root = trie[root][id];
sum[root] ++; //记录数目则需要
}
pos[++ cnt] = root; //记录每个字符串的结束位置 ，通
// 过结束位置上的出现次数判断是否是其他字符串的前缀
} // 若根据输入判断，则不需要这句话，查找输入的字符串最后一个位置的出现次数即可
建trie树
字典树查找模板：
//trie树查找
int serach()//bool serach() , 该字符串为前缀的数目/是否存在以该字符串为前缀的字符串
{
int len = strlen(str);
int rt = ;
for(int i = ; i < len; i ++)
{
int id = str[i] - 'a';
if(!trie[rt][id])
return ;//return false;
rt = trie[rt][id];
}//达到字符串最后一个字符所在位置
return sum[rt]; // return true;
}
字典树查找