`
暴风雪
  • 浏览: 389167 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[后缀数组]ural 1354:Palindrome. Again Palindrome

阅读更多

大致题意:
    给出一个字符串,要求在这个字符串后面添加最少的字母使其成为回文串。

 

大致思路:
    要注意添加的字母数不能为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;
}
 
1
0
分享到:
评论

相关推荐

    在线OJ网址大全在线OJ网址大全

    3. **Ural State University**(&lt;http://acm.timus.ru/&gt;) - **特点**:题库质量高,适合高级选手。 - **适用人群**:适合高级编程学习者。 4. **USACO Gate**(&lt;http://ace.delos.com/usacogate&gt;) - **特点**...

    Python库 | ural-0.28.0.tar.gz

    资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059

    OJ 网址汇总

    * 俄罗斯:乌拉尔大学(URAL)、萨拉托夫大学(SGU)、EL Judge(MIPT) * 西班牙:瓦拉杜利德大学(UVA) * 美国:USACO * 波兰:SPOJ * 吉尔吉斯斯坦:KRSU 学习论坛BBS链接 学习论坛BBS链接是信息学爱好者和...

    PKU 图论 DP 解题报告

    通过分析后缀数组的性质可知,最长的公共前缀一定会出现在后缀数组中相邻位置的两个后缀之间,即height[i]表示了这两个后缀之间的最长公共前缀。因此,只需要遍历后缀数组,检查每一对相邻的后缀是否来自不同的原始...

    Cai0715解题表格1

    - **后缀数组**和**高度数组**:在字符串处理问题中,如PKU 2774和PKU 1743,后缀数组和高度数组用于找到最长公共前缀或最长不可重叠重复子串。 - **二分查找**:在多个题目中,如寻找第K大的数或判断子串是否存在...

    ACM必备书籍及相关网站地址

    1. **数据结构**:书中详细介绍了数组、链表、栈、队列等基本数据结构,并对这些数据结构的应用进行了深入探讨。 2. **排序算法**:对常见的排序算法(如冒泡排序、插入排序、选择排序、快速排序、归并排序等)进行...

    学习C语言的好网站和在线裁判系统 一些网站

    - 俄罗斯托木斯克国立大学(URAL):http://acm.timus.ru/ - 白俄罗斯国立大学(SGU):http://acm.sgu.ru/ - 哈尔滨工业大学(HIT):http://acm.hit.edu.cn/ - 湖南大学(HNU):...

    acm_ural_1099

    【标题】"acm_ural_1099" 是一个与编程竞赛相关的主题,通常在ACM(国际大学生程序设计竞赛)或类似的算法比赛中出现。这类问题旨在测试参赛者解决算法问题的能力,通常需要使用一种或多种编程语言来编写解决方案。 ...

    acm_ural_1148

    标题 "acm_ural_1148" 指向的是一个 ACM(国际大学生程序设计竞赛)问题,这个问题在 Ural University Online Judge(乌拉尔大学在线评测系统)上编号为 1148。描述中的 "Pascal acm_timus_ural_1148.pas" 表明提供...

    1.高逸涵《与圆有关的离散化方法》.ppt

    2. Empire strikes back (ural 1520):这是一个与圆相关的问题,虽然具体细节未给出,但可以推测同样需要运用离散化策略来解决。 总结起来,离散化方法在解决与圆有关的计算问题时,通过将连续的几何对象转换为离散...

    2010FZUACM_高级数据结构习题讲解1

    例如URAL1470 UFOs问题,可以通过三维树状数组来高效解决。 3. **线段树**: - 线段树是一种数据结构,可以用于在线性时间内处理区间查询和区间更新。在POJ2482 Stars in Your Window问题中,由于数值范围很大,...

    Ural URAL 解题思路

    《Ural URAL 解题思路》 在编程竞赛和算法挑战的世界中,Ural University的在线判题系统,简称Ural或URAL,是许多程序员磨炼技能的重要平台。它提供了丰富的算法题目,涵盖数据结构、图论、动态规划、数学等多个...

    URAL部分测试数据

    URAL部分测试数据是针对Timus Online Judge平台的一个竞赛或练习问题的数据集。Timus Online Judge是一个流行的在线编程竞赛和练习平台,它为参赛者提供了一系列的编程题目,以提升编程技能和算法理解能力。这个数据...

    ural部分题解

    "ural部分题解"是一个关于编程竞赛平台Ural(也称为URAL Online Judge或University of Maribor Algorithmic contests)的解题集,由大牛出品。这个资源包含Vol1到Vol3的部分题目解答,虽然不完整,但大约涵盖了200道...

    模式识别课件

    3. 文本ural特征:在文本识别中,词频、n-gram、TF-IDF等方法用于提取文本的关键信息。 4. 频域特征:如傅立叶变换、小波分析等,将信号从时域转换到频域,揭示其内在的周期性和频率信息。 特征选择也非常重要,好...

    hdu pku ural 题目分类

    HDU、PKU和URAL是三个著名的在线编程竞赛平台,它们为程序员提供了丰富的算法题目,帮助参赛者提升编程技能和算法理解能力。这些平台的题目通常涵盖了基础算法、数据结构、数学逻辑等多个方面,对于准备各类编程竞赛...

    各个ACM的网址

    2. Ural: 俄罗斯乌拉尔大学的在线判题系统,提供多种语言支持,适合练习基础到高级的算法题目。 3. Uva (University of Valladolid): 来自西班牙的一站式编程竞赛平台,拥有大量经典题目。 4. Poi: 波兰华沙大学的...

    这些题目涵盖了递归、排序、数据结构等多个方面,是算法学习和刷题的重要资源

    - **URAL**: &lt;http://acm.timus.ru/&gt; - **SPOJ**: &lt;https://www.spoj.com/&gt; - **Codeforces**: &lt;https://codeforces.com/&gt; 这些网站为算法学习者提供了丰富的练习资源。 ### 二、算法书籍推荐 #### 《算法导论...

    ACM网站大全(OJ+代码+贴吧)

    - **俄罗斯 (URAL)**:`http://acm.timus.ru/` - 俄罗斯的一个著名在线评测系统。 - **圣彼得堡国立大学 (SGU)**:`http://acm.sgu.ru/` - 圣彼得堡国立大学的在线评测系统。 - **莫斯科物理技术学院 (MIPT)**:`...

Global site tag (gtag.js) - Google Analytics