- 浏览: 377702 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
给出一个字符串,要求在这个字符串后面添加最少的字母使其成为回文串。
大致思路:
要注意添加的字母数不能为0,要分奇偶讨论。
#include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; const int nMax =1000012; int num[nMax]; int sa[nMax], rank1[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 ++) rank1[sa[i]] = i; for(i = 0; i < n; height[rank1[i ++]] = k){ for(k ? k -- : 0, j = sa[rank1[i]-1]; r[i+k] == r[j+k]; k ++); } } int Log[nMax]; int best[20][nMax]; void initRMQ(int n) {//初始化RMQ for(int i = 1; i <= n ; i ++) best[0][i] = height[i]; for(int i = 1; i <= Log[n] ; i ++) { int limit = n - (1<<i) + 1; for(int j = 1; j <= limit ; j ++) { best[i][j] = min(best[i-1][j] , best[i-1][j+(1<<i>>1)]); } } } int lcp(int a,int b) {//询问a,b后缀的最长公共前缀 a = rank1[a]; b = rank1[b]; if(a > b) swap(a,b); a ++; int t = Log[b - a + 1]; return min(best[t][a] , best[t][b - (1<<t) + 1]); } char str[nMax]; int main(){ int i,j,n,cas=0,len; Log[0] = -1; for(int i=1;i<=nMax;i++){ Log[i]=(i&(i-1))?Log[i-1]:Log[i-1] + 1 ; } while(scanf("%s",str)!=EOF){ len=strlen(str); n=0; for(i=0;i<len;i++){ num[n++]=str[i]; } num[n++]=126; for(i=len-1;i>=0;i--){ num[n++]=str[i]; } num[n]=0; memset(height,0,sizeof(height)); da(num, n + 1,130); calHeight(num,n); initRMQ(n); int start,ans=1,tmp; int ans1=len-1,ans2=len-1; int len1,len2,fuck=0; for(i=len-1;i>0;i--){ tmp=lcp(i,n-i-1); ///首先考虑回文长度是奇数的情况 // printf("1lcp(%d,%d)=%d\n",i,n-i-1,tmp); if(tmp>=len-i){ if(len%2==1&&i==len/2)continue; ans1=i; } tmp=lcp(i,n-i); ///考虑回文长度是偶数的情况 // printf("lcp(%d,%d)=%d len-i=%d\n",i,n-i,tmp,len-i); if(tmp>=len-i){//&&((!len&1)&&i==len/2)){ if(len%2==0){ if(i==len/2){ continue; } } fuck=1; ans2=i; // cout<<"fffuuuccckkk\n"; } } if(len==1){ cout<<str<<str<<endl; continue; } // cout<<ans1<<" "<<ans2<<" "<<fuck<<endl; len1=(ans1)*2+1; len2=ans2*2; if(len1<len2||!fuck){ for(i=0;i<ans1;i++)cout<<str[i]; for(i=ans1;i>=0;i--)cout<<str[i]; cout<<endl; } else{ for(i=0;i<ans2;i++)cout<<str[i]; for(i=ans2-1;i>=0;i--)cout<<str[i]; cout<<endl; } } 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 847题意 http://acm.hdu.edu.cn/ ... -
[离散化+线段树]poj2528
2014-12-01 23:16 580题意 给出每个海报的位置,问最后没有被完全覆盖 ... -
[线段树区间合并]poj 3667
2014-12-01 11:45 750i题意 和poj1823差不多,加了一个查 ... -
[线段树区间更新]poj 1823
2014-12-01 02:56 848题意 一个旅馆有n个房间,有m次操作,每次操作可 ... -
[线段树]poj 3368
2014-11-29 07:58 697题意 给出一串数字,有m次询问,每次询问[ab ... -
[线段树成段更新]poj 2777
2014-11-28 01:33 1087题意: 一段区间从1-n的初始颜色为1,每 ... -
[线段树]poj 2182
2014-11-27 23:13 579题意: n头牛站队,每头牛都有一个属于[ ... -
[线段树]poj 3264
2014-11-27 21:57 468题意 给出一串数字,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 832题意:一个高h宽w的二维空间,每次放进去一个高为1,宽为a的 ... -
[线段树]hdoj 1394
2014-11-24 22:40 893题意 给出一列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 976大致题意: 给出一个长度小于100000的字符串 ... -
[线段树,单点更新]hdoj 1754:I Hate It
2012-10-21 21:33 1229大致题意: 给出一个数组,在线更新点的值,查询区 ...
相关推荐
资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
URAL http://acm.timus.ru 俄罗斯乌拉尔大学在线题库 SGU http://acm.sgu.ru/ 俄罗斯圣萨拉托夫州大学在线题库 ELJ http://acm.mipt.ru/judge/bin/problems.pl?lang=en file:///M|/acm/ACM大量习题题库及建议培养...
Pascal acm_timus_ural_1148.pas
Ural解题思路 Ural解题思路 Ural解题思路 Ural解题思路
Ural
拉尔商店 RalShop是使用MERN堆栈构建的全堆栈电子商务应用程序。 科技栈 蒙哥 表示 ReactJS 节点JS 已安装的套件 ...Cloudinary用于保存图像 Dotenv用于环境变量 ...古尼·乌拉尔(Guney Ural) 执照
chieves t he integration of optical and st ruct ural design sof tware. Mainly based on black box compo2 nent met hod , t he development of optical and st ruct ural design sof tware is completed using ...
Pascal acm_timus_ural_1099.pas
URAL3D
URAL(Timus Online Judge)部分测试数据 不全
Ural1028 Star 密码机(浙江2003省赛)
Ural 1238 源代码 涉及算法(动态规划、贪心、DFS)
在Shopping59.rf网站上进行联合购物扩张 Shopping59.RF - 这是在彼尔姆联合...ural-toys.ru 我们也接受来自其他网站的订单: odezhda-master.ru gepur.com.ua milofo.ru z29.ru butik-duhov.ru 支持语言:русский
ural 题解 yuhch123。 关于yuhch123: ioi2008 金牌第一名,这是当初它做ural 第一卷时的题解
28. The Theoretical Background of the Ural-Altale Hypothesis The hypothesis of common origin of the Altaic languages,and even the Ural-Altaic languages,dates from the first half of the last century....
资源分类:Python库 所属语言:Python 资源全名:ural-0.25.0-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
语言:русский 在网站上的联合购买的扩展59.rf shopping59.rf - 这是烫发中的一个联合...ural-toys.ru。我们还接受来自其他网站的订单:odezhda-master.ru。gepur.com.ua。milofo.ru。z29.ru.Butik-duhov.ru
包含了ural题库中Vol_I 到Vol_III的所有题目的解题思路
部分题解 大牛出品 Vol1-3 不是很全,约有200题左右
URAL-PHA