很是头疼指针,今天写了写发现其实没那么难、、、
如果心中充满了对某事物的畏惧,那么这个事情就很难完成,要有藐视困难的决心,和战胜困难的毅力!吖飒!加油~~~
题意:
统计某个前缀出现的次数。
分析:
很明显需要用字典树写,节省空间节省时间的有效方法。
这里洗需要解决一个问题,记录前缀出现的次数,也就是说,建树时,如果该字母出现过,data+1,如果没出现,data=1;
查找的时候,最后一个字母的data即为所求。
代码(能当字典树模板看):
#include<iostream>
#include<string.h>
using namespace std;
struct Trie
{
int data;
Trie * next[26];
}*p;//声明
void create(char str[],int k,Trie *Head)
{
while(k<strlen(str))
{
if(Head->next[str[k]-'a']!=NULL)
{
Head->next[str[k]-'a']->data+=1;
Head=Head->next[str[k]-'a'];
}
else
{
Head->next[str[k]-'a']=new Trie; // 用Head->next[str[k]-'a']开辟新节点
Head=Head->next[str[k]-'a'];//改变指向,Head指向新节点
for(int j=0;j<26;j++) Head->next[j]=NULL;
Head->data=1;
}
k++;
}
}
int search(char str[],int k,Trie* w)
{
while(k<strlen(str))
if(w->next[str[k]-'a']!=NULL)
w=w->next[str[k++]-'a'];
else return 0;
return w->data;
}
int main()
{
int i;
char animal[15];
p=new Trie;//申请空间
for(i=0;i<26;i++) p->next[i]=NULL;//分配内存
while(gets(animal)&&animal[0]!='\0')
{
create(animal,0,p);
memset(animal,'\0',sizeof(animal));
}
while(~scanf("%s",animal))
{
printf("%d\n",search(animal,0,p));
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树
hdu 1166线段树代码
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
NULL 博文链接:https://128kj.iteye.com/blog/1734821
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类