- 浏览: 377501 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
给出n个字符串。求出至少出现在n/2+1个字符串中的子串中,所有长度最大的子串。
大致思路:
二分+判定。输出的时候要加一个isp判定符,防止输出相同的字符串。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int nMax = 200001; int num[nMax]; int sa[nMax], rank[nMax], height[nMax]; int wa[nMax], wb[nMax], wv[nMax], wd[nMax]; int cmp(int *r, int a, int b, int l){ return r[a] == r[b] && r[a+l] == r[b+l]; } void da(int *r, int n, int m){ // 倍增算法 r为待匹配数组 n为总长度 m为字符范围 int i, j, p, *x = wa, *y = wb, *t; for(i = 0; i < m; i ++) wd[i] = 0; for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++; for(i = 1; i < m; i ++) wd[i] += wd[i-1]; for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] = i; for(j = 1, p = 1; p < n; j *= 2, m = p){ for(p = 0, i = n-j; i < n; i ++) y[p ++] = i; for(i = 0; i < n; i ++) if(sa[i] >= j) y[p ++] = sa[i] - j; for(i = 0; i < n; i ++) wv[i] = x[y[i]]; for(i = 0; i < m; i ++) wd[i] = 0; for(i = 0; i < n; i ++) wd[wv[i]] ++; for(i = 1; i < m; i ++) wd[i] += wd[i-1]; for(i = n-1; i >= 0; i --) sa[-- wd[wv[i]]] = y[i]; for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++){ x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1: p ++; } } } void calHeight(int *r, int n){ // 求height数组。 int i, j, k = 0; for(i = 1; i <= n; i ++) rank[sa[i]] = i; for(i = 0; i < n; height[rank[i ++]] = k){ for(k ? k -- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k ++); } } int loc[nMax],m; char str[nMax],res[nMax]; bool vis[1004]; bool check(int mid,int len){ int i,j,tot; tot=0; memset(vis,0,sizeof(vis)); for(i=2;i<=len;i++){ if(height[i]<mid){ memset(vis,0,sizeof(vis)); tot=0; } else{ if(!vis[loc[sa[i-1]]]){ vis[loc[sa[i-1]]]=1; tot++; } if(!vis[loc[sa[i]]]){ vis[loc[sa[i]]]=1; tot++; } if(tot>m/2){ // for(j=0;j<mid;j++){ // res[j]=num[sa[i]+j]+'a'-1; // }res[mid]='\0'; return 1; } } } return 0; } void print(int mid,int len){ int i,j,tot; tot=0; int isp=0; memset(vis,0,sizeof(vis)); for(i=2;i<=len;i++){ if(height[i]<mid){ isp=0; memset(vis,0,sizeof(vis)); tot=0; } else{ if(!vis[loc[sa[i-1]]]){ vis[loc[sa[i-1]]]=1; tot++; } if(!vis[loc[sa[i]]]){ vis[loc[sa[i]]]=1; tot++; } if(tot>m/2&&!isp){ for(j=0;j<mid;j++){ res[j]=num[sa[i]+j]+'a'-1; }res[mid]='\0'; printf("%s\n",res); isp=1; } } } } int main(){ int n,k,i,j,a,b,sp,ans; while(scanf("%d",&m)&&m){ sp=29; //分隔符 n=0; ans=0; for(i=1;i<=m;i++){ scanf("%s",str); for(j=0;str[j];j++){ loc[n]=i; num[n++]=str[j]-'a'+1; } loc[n]=sp; num[n++]=sp++; } if(m==1){ printf("%s\n",str); continue; } num[n]=0; da(num, n + 1, sp); calHeight(num,n); int left=0,right=strlen(str),mid;//开始二分 while(right>=left){ mid=(right+left)/2; if(check(mid,n)){ //判断长度为mid的串是否是所有字符串的公共子串 left=mid+1; ans=mid; } else{ right=mid-1; } } if(ans!=0){ print(ans,n); printf("\n"); // printf("%s\n",res); } else{ printf("?\n"); printf("\n"); } } return 0; }
发表评论
-
[树状数组]poj 2299
2014-12-13 20:58 1872题意 求一列数字的逆序数。 思路 ... -
[树状数组]hdoj 1166
2014-12-12 01:21 2题意 http://acm.hdu.edu.cn/ ... -
[树状数组]hdoj 1166
2014-12-12 01:21 846题意 http://acm.hdu.edu.cn/ ... -
[离散化+线段树]poj2528
2014-12-01 23:16 579题意 给出每个海报的位置,问最后没有被完全覆盖 ... -
[线段树区间合并]poj 3667
2014-12-01 11:45 750i题意 和poj1823差不多,加了一个查 ... -
[线段树区间更新]poj 1823
2014-12-01 02:56 847题意 一个旅馆有n个房间,有m次操作,每次操作可 ... -
[线段树]poj 3368
2014-11-29 07:58 695题意 给出一串数字,有m次询问,每次询问[ab ... -
[线段树成段更新]poj 2777
2014-11-28 01:33 1087题意: 一段区间从1-n的初始颜色为1,每 ... -
[线段树]poj 2182
2014-11-27 23:13 578题意: n头牛站队,每头牛都有一个属于[ ... -
[线段树]poj 3264
2014-11-27 21:57 466题意 给出一串数字,m个询问,对于每次询问求出 ... -
[线段树成段更新]hdoj 1698
2014-11-27 21:00 684题意: 对一个线段上的值进行修改,一次可以把[i, ... -
[线段树成段更新]poj 3468
2014-11-27 12:43 661题意: 给出一串n个数,每次操作分为两种,分 ... -
[线段树]poj 2828
2014-11-26 22:02 686题意 n个人插队,每次某个人都会选择插入第i个 ... -
[线段树]hdoj 2795
2014-11-25 20:33 831题意:一个高h宽w的二维空间,每次放进去一个高为1,宽为a的 ... -
[线段树]hdoj 1394
2014-11-24 22:40 892题意 给出一列n个数字,每一个数字都和其他 ... -
[后缀数组]acdream 1430
2014-10-16 14:08 501大致题意: 求出一个字符串(len<=1 ... -
[KMP+乱搞]hdoj 4749
2014-10-11 15:22 741大致题意: 求文本串中最多能选出多少子串,使得这 ... -
[KMP]hdoj 4763
2014-10-10 11:39 657题意: 给出一个字符串,问是否存在这样的子串E使得 ... -
[后缀数组][二分]hdu 5008
2014-09-27 10:10 975大致题意: 给出一个长度小于100000的字符串 ... -
[线段树,单点更新]hdoj 1754:I Hate It
2012-10-21 21:33 1224大致题意: 给出一个数组,在线更新点的值,查询区 ...
相关推荐
poj 3294 Life Forms.md
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1757060
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1754756
NULL 博文链接:https://128kj.iteye.com/blog/1746750
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
这是西北工业大学的POJ试题的答案,欢迎下载!
NULL 博文链接:https://128kj.iteye.com/blog/1747400
网上整理的一些poj刷题指南。 poj地址:http://poj.org
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
NULL 博文链接:https://128kj.iteye.com/blog/1745671
只是poj上的一条题目,对于理解后缀数组很有帮助.poj3261
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
twilight-poj-solutionPOJ () solution by twilight想当年要找一题的分析, 解答实在太难了现在都是开源的时代了, 干脆把Archive放到GitHub上, 供后来人参考.POJ ID: 部分题解: 转载请注明出处~
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
leetcode 2 和 c 实践 C++ ###数据结构和算法 大批 加一: # 合并排序数组:# 排序 搜索 二分查找:代码、#、#、# 选择 数组中第 K 个最大元素:# 递归 ...动态规划:LeetCode#xx、POJ#xx 后缀数组
POJ 3267 POJ 1260 POJ 1015 POJ 3176 POJ 1080 POJ 1159 POJ 2533 POJ 1836 Leetcode 70 Leetcode 309 搜索 DFS POJ 2488 POJ 3083 POJ 3009 POJ 1321 BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索...
poj上的题,音乐主题,首先需要对给定的数组差分,之后就是用后缀数组就行
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...