- 浏览: 12069 次
最新评论
poj 3294 Life Forms 求n(n>1)个字符串的最长的一个子串 后缀数组
- 博客分类:
- 技术杂绘
Description You may have wondered why most extraterrestrial life forms resemble humans, differing by superficial traits such as height, colour, wrinkles, ears, eyebrows and the like. A few bear no human resemblance; these typically have geometric or amorphous shapes like cubes, oil slicks or clouds of dust. The answer is given in the 146th episode of Star Trek - The Next Generation, titled The Chase. It turns out that in the vast majority of the quadrant's life forms ended up with a large fragment of common DNA. Given the DNA sequences of several life forms represented as strings of letters, you are to find the longest substring that is shared by more than half of them. Input Standard input contains several test cases. Each test case begins with 1 ≤ n ≤ 100, the number of life forms. n lines follow; each contains a string of lower case letters representing the DNA sequence of a life form. Each DNA sequence contains at least one and not more than 1000 letters. A line containing 0 follows the last test case. Output Sample Input Sample Output bcdefg cdefgh ?#include #include #include #include using namespace std; ///后缀数组 倍增算法 const int maxn=500000; char str[maxn]; int wa[maxn],wb[maxn],wv[maxn],wn[maxn],a[maxn],sa[max n]; int cmp(int* r,int a,int b,int l) {return r[a]==r[b]&&r[a+l]==r[b+l];} /**n为字符串长度,m为字符的取值范围,r为字符串。后面的j为每次排 序时子串的长度*/ void DA(int* r,int* sa,int n,int m) { int i,j,p,*x=wa,*y=wb,*t; ///对R中长度为1的子串进行基数排序 for(i=0;i=0;i--)sa[--wn[x[i]]]=i; for(j=1,p=1;p=j)y[p++]=sa[i]-j; ///基数排序 for(i=0;i=0;i--)sa[--wn[wv[i]]]=y[i]; ///当p=n的时候,说明所有串都已经排好序了 ///在第一次排序以后,rank数组中的最大值小于p,所以让m=p for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i字符串后面添加了一个0号字符,所以它必然是最小的 一个后缀。而字符串中的其他字符都应该是大于0的(前面有提到,使用倍 增算法前需要确保这点),所以排名第二的字符串和0号字符的公共前缀 (即height[1])应当为0.在调用calheight函数时,要注意height数组的范 围应该是[1..n]。所以调用时应该是calheight(r,sa,n) 而不是calheight(r,sa,n+1)。*/ int rank[maxn],height[maxn]; void calheight(int* r,int* sa,int n) { int i,j,k=0; for(i=1;i字符串的最长的一个子串 int n=0;//总字符串长度 int m;//字符串个数 int l,r; int belong[maxn];//属于第几个字符串 int cnt[200]; int _check( int mid ){ memset(cnt,0,sizeof(cnt)); int flag= 1, ans= 0; for( int i= 1; i字符串 if( ans>= m/ 2+ 1 ) return 1; } return 0; } void print( int mid ){ memset(cnt,0,sizeof(cnt)); int ans= 0, flag= 1, isp= 0, beg; for( int i= 1; i= (m/ 2+ 1 ) ){ isp= 1; for( int j= 0; j字符串 for(int i=0;i字符串的最长的一个子串,满足该子串在超过一半以上的字符串 中出现过,并输出该子串,如果有多个子串满足要求,则按字典序输出所有的子串; 算法:二分长度+后缀数组 将n个字符串连起来,中间用不相同的且没有出现在字符串中的字符隔开,求 后缀数组。然后二分答案,将后缀分成若干组,判断每组的后缀是否出现在不 小于k个的原串中。这个做法的时间复杂度为O(nlogn)*/ while(scanf("%d",&m)==1&&m) { n=0; for(int i=1;i>1; if(_check(mid)) l=mid+1; else r=mid; } int ans=r-1; if(!ans) printf("?\n"); else print(ans); printf("\n");//题目要求多输出一个空行 } return 0; }
发表评论
-
Java 正则表达式使用心得
2012-07-06 09:46 581Greedy 数量词和Reluctant 数量词的区别。 ... -
可编程计算组件-Apace实时数据库产品
2012-07-03 13:44 790可编程计算组件面向的客户要求比较高,但其主要目的是提供给软 ... -
纪念Rokon停止更新――从零开始用Rokon开发一个小游戏
2012-07-02 13:00 952懒骨头你给我听着:你有健康的家人~满意的工作~未知的女友~ ... -
adobe Air 小玩意程序:加载百度随便听听
2012-07-02 13:00 640今天,我承认会有一点偷懒,在写微博的程序的时候,忽然 ... -
flash player的重绘渲染机制
2012-07-02 13:00 610先简洁说下前人的研究成果。 一个是Tencent的Y ... -
Hello Android
2012-07-02 13:00 679虚心是知识的向导,恒心是知识的保管。 ... -
imx515 开发板Android源代码编译过程[开发日记]
2012-07-02 13:00 963Android requires the followin ... -
as连接fms
2012-07-01 10:33 676如果 ActionScript 3.0 SWF 文件需要与 ... -
WebService另一种轻量级实现―Hessian 学习笔记
2012-07-01 10:33 646最近和同事聊天,得知他们在使用一种叫做Hessian的We ... -
关于The serializable class XXX does not declare a static final serialVersionUID field of type long的警告
2012-07-01 10:33 657最近在研究Java与Flex用Json交换数据,也就是Ja ... -
Flex Socket编程
2012-07-01 10:33 601比较懒,比较少上csdn的,如果发现留言给我没有回复,望见 ... -
Flex4与java通信(二、与servlet通信)
2012-07-01 10:33 585说明:这里介绍使用URLRequest+URLLoader ... -
Flex学习笔记(1)
2012-06-30 16:56 573Flex学习笔记(1) 2010年06 ... -
Flex Ant编译模板
2012-06-30 16:56 687Flex Ant编译模板 2010年07月16日 Fl ... -
Flex mobile入门
2012-06-30 16:56 567Flex mobile入门 2010年12月 ... -
Flex编程学习基础
2012-06-30 16:56 573Flex编程学习基础 2010年11月08日 Flex是 ... -
flex RSL模式
2012-06-30 16:56 337flex RSL模式 2010年09月13 ...
相关推荐
poj 3294 Life Forms.md
poj 2744子串 答案 所用的是最简单的C语言
北大POJ1016-Numbers That Count【字符串处理】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1744222
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
北大POJ3239-Solution to the n Queens Puzzle 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1757060
NULL 博文链接:https://128kj.iteye.com/blog/1744555
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1747400
北大POJ2002-Squares 解题报告+AC代码
上面可能有poj的题目,hdu的题目,spoj的题目,sgu的题目,hust上的题目,fzu上的题目
功能说明此函数返回单个字符串或字符串中字符串的长度单元阵列或矩阵。...%%%%%%%% 输入: S = 字符串数组或... 试试这个: S = {'abc','2D','1','gavlvvglbv','guDVWF FIUWWFH ihf poj','gtwe66etr2rrhndm\['} L = strin
只是poj上的一条题目,对于理解后缀数组很有帮助.poj3261
NULL 博文链接:https://128kj.iteye.com/blog/1745671
简单地poj1001代码,是典型的利用数组输出结果的方法,关键的是测试数据。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
人们熟悉的四则运算表达式称为中缀表达式,例如(23+34*45/(5+6+7))。在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又...给定一个中缀表达式,编写程序,利用堆栈的方法,计算表达式的值。
1、前序遍历的第一个字母必是 根 2、在中序遍历的字母串中找出 根字母,那么根字母左右两边的字符串就分别是它的左、右子树 3、利用递归复原二叉树(把子树看作新的二叉树) 4、后序遍历特征:后序遍历字母串 自右至...