这题内存需求很大,我用静态数组写的trie总MLE,看discuss说50w的数组才过,但我一开50w的就MLE了啊……想不通
这是链表版的trie,1个case,所以也不用考虑内存释放什么的
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct trie
{
struct trie *son[26];
int n;
}*root;
inline int idx(char &a)
{
return a-'a';
}
void insert(char *s)
{
int i,j;
struct trie *c,*newnode;
c=root;
for(i=0;s[i];i++)
{
if(c->son[idx(s[i])]!=0)
{
c=c->son[idx(s[i])];
c->n++;
}
else
{
newnode=(struct trie *)malloc(sizeof(struct trie));
for(j=0;j<26;j++) newnode->son[j]=0;
c->son[idx(s[i])]=newnode;
c=newnode;
c->n=1;
}
}
}
int find(char *s)
{
int i;
int len;
struct trie *c;
len=strlen(s);
if(len==0) return 0;
c=root;
for(i=0;i<len;i++)
{
if(c->son[idx(s[i])]!=0)
{
c=c->son[idx(s[i])];
}
else return 0;
}
return c->n;
}
int main()
{
char a[11];
int i;
root=(struct trie *)malloc(sizeof(struct trie));
for(i=0;i<26;i++) root->son[i]=0;
root->n=0;
while(gets(a),strcmp(a,"")!=0)
insert(a);
while(gets(a)!=0)
printf("%d\n",find(a));
return 0;
}
分享到:
相关推荐
hdu 1166线段树
hdu 1166线段树代码
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
总结来说,"二叉搜索树练习 HDU3791"是一道关于二叉搜索树操作的编程题,可能需要实现插入、删除、查找等基本操作,并通过分析`Main.java`源码来理解和解决问题。同时,可能需要借助各种工具进行调试和测试,以确保...
ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
杭电ACM课件2014版之 (HDUACM201403版_04)递推求解
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS)、树的遍历(前序、中序、后序)以及最小生成树、最短路径等算法。 9. **动态规划**:这是一种优化策略,通过构建状态转移方程来...
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
2. **数据结构**:常用的数据结构包括数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图等,对于不同的问题,选择合适的数据结构能有效提高解题效率。 3. **字符串处理**:杭电ACM中的题目可能涉及到...
hdu2101AC代码