- 浏览: 388613 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (229)
- java编程 (4)
- java实用程序 (2)
- 算法设计 (34)
- 数据库 (8)
- ACM模板 (12)
- 技术术语 (1)
- java_web (3)
- php (22)
- eclipse (3)
- linux (25)
- linux命令使用心得 (3)
- web服务器 (8)
- IT知识 (2)
- 前端技术 (17)
- 开源软件 (5)
- vim (3)
- linux多线程 (9)
- web开发经验 (3)
- lua (5)
- linux编程 (3)
- smarty (1)
- mysql (4)
- Hive (2)
- 数据挖掘 (9)
- python (2)
- 生活 (1)
- C++ (2)
- 计算机 (1)
- objective-c (11)
- css (2)
- 游戏 (1)
- Mac (1)
最新评论
-
lr544463316:
我的怎么不行呀.....
Mysql Access denied for user ''@'localhost' to database 的一种解决方法 -
babaoqi:
使用时需要注意group_concat函数返回值的最大长度=g ...
mysql中的group_concat函数 -
代码能力弱成渣:
可以帮我看下我的代码么?我自己写的sam,也有ac过题的,但是 ...
求两个字符串的最长公共连续子序列(SAM实现) -
atgoingguoat:
有1000个?不过还是收藏下。
jquery常用的插件1000收集(转载)
/* * AC自动机,每个节点 添加一个d表示节点代表的字符串的查询类型1表示只有查询0,2表示只有查询1,3表示有查询 * 0和查询1,len表示该节点代表的字符串的长度。 */ #include <cstdio> #include <cstring> #include <map> using namespace std; const int N=100005*6; //节点个数的最大值 const int S=26; //不同的字符 个数 const int L=100005; struct node{ node *sons[S], *fail; int num; //该节点出现的次数 int d; int len; }nodes[N], *root; int cnt; //cnt是树中节点的 个数 node *que[N]; char text[L]; int ids[L], type[L], nums[2][N], last[N]; int n; void clear(){ cnt=0; root=NULL; } node* newNode(){ node* ans=&nodes[cnt++]; memset(ans->sons, 0, S*sizeof(node*)); ans->fail=NULL; ans->num=0; ans->d=0; return ans; } int hash(char ch){ //字符的哈希函数,根据不同的需要而定 return ch-'a'; } int id(node*& t){ //计算该节点的id return t-nodes; } //j表示当前关键字的标号 int insert(node*& root, char* str, int d){ node* t=root; int i, k; for(i=0; str[i]; i++){ if(t->sons[k=hash(str[i])]==NULL){ t->sons[k] = newNode(); } t->len=i; t=t->sons[k]; } t->len=i; t->num++; t->d|=d; return id(t); } void getFail(node*& root){ int l, r, i; node *t; l=r=0; root->fail=root; //这样可以保证每个节点的fail指针都是非空的 for(que[r++]=root; l!=r; ){ t=que[l++]; for(i=0; i<S; i++){ if(t->sons[i]){ que[r++]=t->sons[i]; if(t==root){ t->sons[i]->fail=t; }else{ t->sons[i]->fail=t->fail->sons[i]; } }else{ //增设虚拟节点 if(t==root) t->sons[i]=t; else t->sons[i]=t->fail->sons[i]; } } } } bool input(){ if(scanf("%s", text)==EOF) return false; clear(); root=newNode(); scanf("%d", &n); int i; char str[7]; for(i=0; i<n; i++){ scanf("%d%s", type+i, str); ids[i]=insert(root, str, 1<<type[i]); } return true; } int ca=0; void solve(){ int i; node *t, *p; for(i=0; i<cnt; i++){ last[i]=-1; nums[0][i]=nums[1][i]=0; } getFail(root); for(t=root, i=0; text[i]; i++){ t=t->sons[hash(text[i])]; for(p=t; p!=root; p=p->fail){ if(p->num>0){ if(p->d&1){ nums[0][id(p)]++; } if(p->d&2){ if(i-p->len+1>last[id(p)]){ nums[1][id(p)]++; last[id(p)]=i; } } } } } printf("Case %d\n", ++ca); int k; for(i=0; i<n; i++){ if(type[i]==0){ k=0; }else{ k=1; } k=nums[k][ids[i]]; printf("%d\n", k); } printf("\n"); } int main(){ //freopen("in.txt", "r", stdin); while(input()) solve(); return 0; }
发表评论
-
升序数组中求一个key出现的次数
2013-01-09 23:08 1109算法思路: 在排好序的数组,相同的数字是排列在一起的,所以只需 ... -
判断单链表是否有环
2013-01-08 19:07 921算法思路: 指针p1和p2的起始值均为链表的表头,指针p1每次 ... -
hdu3684
2011-11-15 20:11 931/* 刚开始打了个记录上下左右四个点的,一直tle。 ... -
hdu3686
2011-11-14 20:43 1035/* 无向图边的双连通分量,在同一个连通分量里的边之间 ... -
poj3968
2011-11-14 04:45 1415source: http://poj.org/problem ... -
uva2819
2011-11-13 02:20 900source: http://livearchive.onli ... -
manacher算法
2011-11-11 00:06 2434const int LEN=110005; const ... -
hdu4118
2011-11-09 21:53 1192枚举每条边最多被经过的次数即可 #include ... -
hdu4115
2011-11-09 16:27 1040source: http://acm.hdu.edu.cn/ ... -
uva(Transitive Closure)
2011-11-08 14:45 918source: http://livearchive.onli ... -
zoj3500
2011-11-07 17:41 956求两个球的体积交或者并 #include <cs ... -
zoj3545
2011-11-04 18:18 868/* AC自动机 相当暴力的 解法: mark[i ... -
zoj3190
2011-11-04 17:34 1317/* * AC自动机,先对资源串和病毒串构成的字符串 ... -
poj3691(DNA Repair)
2011-11-04 13:18 1481/* AC自动机,增设虚拟节点,求长度为n的字符串中包 ... -
hdu2825
2011-11-04 11:53 993/* AC自动机,增设虚拟节点,求长度为n的字符 ... -
hdu4095
2011-11-03 13:19 1020/* 第一步,构建BST,用第一个数作为bst的 ... -
zoj3540
2011-11-02 21:33 927/* 其实就是把总共的 放置次数减去不能放置的那些就行 ... -
poj1741(树的分治,基于边的 分治)
2011-11-02 20:25 3358/* 树基于边的分治算法,计算树中距离小于等于k的点 ... -
hdu2939
2011-10-29 18:36 859source: http://acm.hdu.edu.cn/s ... -
hdu3982
2011-10-29 10:20 948//半平面交+多边形和圆的交的面积 #include ...
相关推荐
【标题】"ZOJ 1002" 是一个在线编程竞赛题目,源自ZOJ(Zhejiang Online Judge),这是一个面向ACM/ICPC(国际大学生程序设计竞赛)的在线评测系统。题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法...
【标题】"zoj 源码700题"是指一个包含700多道ZOJ(在线判题系统Zhejiang Online Judge)编程竞赛题目的源代码集合。这个资源对于学习算法、提高编程技能以及准备编程竞赛的学员来说极具价值。 【描述】"包含了zoj...
ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...
标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...
浙江大学ZOJ(Zhejiang University Online Judge)是一个在线编程练习平台,主要服务于计算机科学和技术的学习者,特别是对算法和编程有浓厚兴趣的学生。这个平台提供了大量的编程题目,涵盖了各种难度和主题,帮助...
【ZOJ.zip】是一个压缩包,里面包含了与ZOJ(Zhejiang Online Judge)相关的ACM(International Collegiate Programming Contest)题解。ZOJ是一个在线编程竞赛平台,它为参赛者提供了一系列算法题目进行练习,以...
【标题】"ZOJ1027解题指南"是一个针对特定编程竞赛题目——ZOJ1027的解决方案集合。ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题...
Problem Arrangement zoj 3777
ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,主要面向计算机科学与信息技术的学生和爱好者,提供了大量的算法题目供参赛者练习和提交代码。"ZOJ题目答案源码"是一个压缩包文件,其中包含了700多道...
zoj 题库 详细解答 解题代码 该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该...
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
《ZOJ 4041问题的正确解法与程序分析》 ZOJ(Zhejiang Online Judge)是一个知名的在线编程竞赛平台,其中的题目编号为4041的题目吸引了众多程序员的关注。本篇文章将深入探讨ZOJ 4041的正确解法,并对提供的源代码...
ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...
标题“ZOJ1014.zip_zoj code_zoj1004”表明这是一个与ZOJ(ZeroJudge)在线判题系统相关的代码压缩包,其中可能包含了解决ZOJ问题1004的源代码。ZOJ是面向编程爱好者和学生的一个在线编程竞赛平台,它提供了各种算法...
**ZOJ月赛题解 (ZOJ Monthly, August 2014)** ZOJ(Zhejiang Online Judge)是中国著名的在线编程竞赛平台之一,它为程序员和学生提供了丰富的算法练习和比赛机会。2014年8月的ZOJ月赛是一场面向广大编程爱好者的...
ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,尤其在ACM(国际大学生程序设计竞赛)领域中有着广泛的影响力。这个“ZOJ题解集合-截至2835”显然是一份包含了大量ZOJ题目解决方案的压缩包,其中涵盖了...
zoj 1003 c语言的,要写这么多描述吗。。
标题 "zoj2536.rar_zoj25" 暗示这是一份与ZOJ(中国大学在线编程竞赛)第2536号问题相关的提交文件,可能包含了参赛者或教练的代码解决方案。描述中的“这个不是用贪心做的”表明该问题可能涉及到一种非贪心算法的...
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
标题 "zoj 1140-zju 2433 简单题的部分答案" 暗示了这是一个关于编程竞赛题目的解答集合,其中涵盖了ZOJ(浙江大学在线评测系统)上的两道题目——ZOJ 1140 和 ZJU 2433。这些题目可能属于算法或数据结构的范畴,...