HDU 1251 统计难题(字典树计算前缀数量)
2024-09-03 23:35:13
字典树应用,每个节点上对应的cnt是以它为前缀的单词的数量
#include<stdio.h>
#include<string.h>
struct trie
{
int cnt;
trie *next[];
};
trie *root=new trie;
void insert(char ch[])
{
trie *p=root,*newnode;
for(int i=; ch[i]!='\0'; i++)
{
if(p->next[ch[i]-'a']==)
{
newnode=new trie;
for(int j=; j!=; j++)
{
newnode->next[j]=NULL;
}
newnode->cnt=;
p->next[ch[i]-'a']=newnode;
p=newnode;
}
else
{
p=p->next[ch[i]-'a'];
p->cnt++;
}
}
}
int find(char ch[])
{
trie *p=root;
for(int i=; ch[i]!='\0'; i++)
{
if(p->next[ch[i]-'a']!=NULL)
p=p->next[ch[i]-'a'];
else
return ;
}
return p->cnt;
}
int main()
{
char ch[];
for(int i=; i!=; i++)
{
root->next[i]=NULL;
}
root->cnt=;
while(gets(ch)) //±ØÐëÓÃgets
{
if(!strcmp(ch,"")) break;
insert(ch);
}
while(scanf("%s",ch)!=EOF)
{
printf("%d\n",find(ch));
}
return ;
}
最新文章
- Linux历史
- 错误 undefined reference to __cxa_guard_acquire/release
- 【BZOJ】【1044】【HAOI2008】木棍分割
- java_设计模式_组合模式_Composite Pattern(2016-08-12)
- Nuget 相关
- python学习day10
- Cocos2d-x Layout简单使用
- [iOS Animation]-CALayer 定时器动画
- String str=";abc";;和String str2=new String(";abc";);有什么区别?
- CSS效果:简单的登录框
- HDU 6348 序列计数 (树状数组 + DP)
- Codeforces543 B. Destroying Roads
- Python 分布式进程
- 23.Hibernate-基础.md
- iOS网络请求安全认证(JWT,RSA)
- mooc linux学习总结
- 【Kafka】Kafka-配置参数详解-参数调优
- [Kubernetes]Kubernetes的网络模型
- unity-----------------------四元数与欧拉旋转方法
- Android 获取联系人和电话号码
热门文章
- Bank Interest
- AS3.0中用于网络通信的类总结
- ios layer 动画
- 求最大公约数(GCD)的两种算法
- 【我与一道水题的抗争之路】 哈理工2323 Emirp(反素数)
- org.hibernate.PropertyNotFoundException: Could not find a getter for employee in class com.itcast.f_hbm_oneToMany.Department
- kill -0
- Kickstart 自动化安装配置
- 登录数据库后,use db很慢的问题
- POI获取Excel列数和行数的方法