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

[后缀数组+RMQ]ural 1297:Palindrome

阅读更多

大致题意:

    给出一个字符串,求出这个字符串中最长的回文串。如果有多个回文串的长度相等且都是最大,则输出最靠前的那个。

 

大致思路:

    首先肯定是要把原字符的逆序串接到原字符串的后面。然后便是从0~~len扫描这个字符串,假设第i个位置是一个回文的中心,然后求出i个i对应位置的lca的最大值即可。每次枚举时要分奇偶两种情况考虑。 

    献上两组数据:qweRTYewq    zzzdzaadzzz 

 

 

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int nMax =1000012;

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 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 = rank[a];    b = rank[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;
        da(num, n + 1,130);
        calHeight(num,n);
        initRMQ(n);
        int start,ans=1,tmp;
        for(i=0;i<len;i++){
            tmp=lcp(i,n-i-1);    ///首先考虑回文长度是奇数的情况
            if(tmp*2-1>ans){
                ans=tmp*2-1;
                start=i-tmp+1;
            }
            tmp=lcp(i,n-i);    ///考虑回文长度是偶数的情况
            if(tmp*2>ans){
                ans=tmp*2;
                start=i-tmp;
            }
        }
        if(ans==1)printf("%c\n",str[0]);
        else{
            for(i=start;i<start+ans;i++){
                printf("%c",str[i]);
            }printf("\n");
        }
    }
    return 0;
}
0
0
分享到:
评论

相关推荐

    详细解析后缀数组(RMQ及LCP)

    后缀数组是字符串处理中的一种重要数据结构,它在计算机科学特别是文本算法领域扮演着关键角色。后缀数组能够提供一种高效的方式来存储和查询字符串的后缀,这使得它成为解决许多字符串问题的有效工具,例如查找模式...

    后缀数组资料打包(论文+PPT+笔记)

    4. **编辑距离**:后缀数组结合其他数据结构(如LCP数组和RMQ(Range Minimum Query))可以快速计算两个字符串的编辑距离。 5. **AC自动机**:后缀数组是构建AC自动机的基础,用于支持多个模式的并行匹配。 ### ...

    后缀数组PPT详细解答

    本文将深入探讨后缀数组及其相关概念,包括SA(Suffix Array)、Height、RMQ(Range Minimum Query)以及多串匹配。 首先,让我们理解什么是后缀数组(Suffix Array)。后缀数组是字符串的所有后缀按字典序排序后的...

    后缀数组 后缀数组.pdf

    在字符串处理的背景下,后缀数组的k-前缀比较关系、名次数组Rank、基数排序、以及最长公共前缀的RMQ问题都是需要掌握的关键知识点。名次数组Rank实际上是后缀数组的辅助数据结构,用于快速查询某个后缀在排序后的...

    后缀数组C++实现代码

    根据给定的信息,本文将详细解释“后缀数组C++实现代码”中涉及的重要知识点,包括后缀数组、倍增算法、以及RMQ(Range Minimum Query)问题。 ### 一、后缀数组 #### 1.1 定义 后缀数组是一种数据结构,它存储了...

    后缀数组1

    关键词包括:字符串、后缀、k-前缀比较关系、后缀数组、名次数组、后缀树、倍增算法、基数排序、最长公共前缀、RMQ问题、模式匹配、回文串和最长回文子串。 总的来说,后缀数组是字符串处理中的重要工具,它提供了...

    后缀数组倍增算法实现

    结合这两个知识点,我们可以构建一个系统,先用倍增算法构建后缀数组,然后利用ST算法实现的RMQ功能来快速查询字符串中某段后缀的最小值,这对于分析字符串性质或者进行特定的字符串搜索任务非常有用。在实际应用中...

    RMQ以及LCA:最近公共祖先

    给定一个数组`A[1...n]`,对于任意的两个索引`i`和`j` (`i ≤ j`),RMQ问题的目标是在`A[i...j]`区间内找到最小值的位置或最小值本身。这是一个非常基础但又非常实用的问题,在许多动态规划和数据结构问题中都有应用...

    rmq-win:RabbitMQ码头工人形象

    rmq-docker-win docker build -t gsxsolutions/rmq:3.5.4 -f .\Dockerfile.3.5.4 . docker build -t gsxsolutions/rmq:3.7.4 -f .\Dockerfile.3.7.4 . docker build -t gsxsolutions/rmq:3.7.5 -f .\Dockerfile....

    Suffix小结.txt

    ### 后缀数组(Suffix Array)详解 #### 引言 后缀数组是计算机科学领域内一种高效的数据结构,主要用于字符串处理,特别是模式匹配、文本分析等场景。它能够快速定位一个子串在主串中的位置,对于解决复杂的字符...

    常用数据结构 - C语言实现

    NOTONLLY的后缀数组模板.cpp RMQ-ST算法.cpp RMQ线段树.cpp SBT.cpp SBT2.cpp splay伸展树.cpp ST表.cpp Treap.cpp Trie树.cpp 二叉堆.cpp 二维线段树.cpp 后缀数组.cpp 后缀数组模板.cpp 块状链表.cpp 左偏树 (2)....

    Alone_L模板1

    此外,代码中还提到了RMQ(Range Minimum Query,区间最小值查询)版本的后缀数组,这表明可能在处理后缀数组时,也考虑了区间内的最小值查询问题,这对于某些特定的应用场景非常有效。 总结起来,后缀数组是字符串...

    双回文子串的相关解法

    - **后缀数组**:构建后缀数组,并计算height数组。 - **最长回文子串预处理**:预处理以每个位置为中心的最长回文子串。 - **结构体数组**:构造一个结构体数组存储每个回文子串的左边界和中心位置,并按左边界排序...

    RMQ-Animations:RMQ 动画应用

    RMQ 动画 这是用于创建文档中说明的动画的应用程序。 这个 repo 是一个简单的应用程序,用于说明 RMQ 可用的动画: rmq(my_view).animations.fade_in rmq(my_view).animations.fade_out rmq(my_view).animations....

    山东大学ACM模板_数据结构.pdf

    12. **后缀数组**:后缀数组是字符串处理中的一种数据结构,用于快速访问字符串的所有后缀,常用于模式匹配和文本分析。 13. **归并树**:归并树(Merge Sort Tree)是基于归并排序构建的数据结构,用于高效地处理...

    ACMer需要掌握的算法讲解 (2).docx

    ACM算法讲解 本文将对ACM主要算法进行讲解,涵盖了基本算法、图算法、数据结构、搜索、计算几何学、动态规划和综合题等多方面的知识点。 一、基本算法 ... + 后缀数组、后缀树 + 块状链表 + 哈夫曼树

    字符串进阶前导知识1

    在处理字符串问题时,RMQ算法有时能与其他数据结构(如后缀数组、线段树等)结合,提供高效的解决方案。 总结起来,掌握字符串哈希和后缀数组是提升在字符串处理领域技能的关键。通过学习哈希,我们可以快速比较...

    rmq.io:Rabbitmq像socket.io

    RMQ.io 您是否要构建可靠且易于编码的连接服务?Rmq.io的任务rmq.io的任务是使RabbitMQ的发布订阅变得容易1,2,3基本原理一个可靠且简单的pubsub并不容易找到。 RabbitMQ是功能强大的消息队列,它具有许多功能,对于...

    compat-libstdc.rpm文件

    `compat-libstdc.rpm` 文件是Oracle数据库安装过程中经常遇到的一个依赖组件,它主要用于解决旧版本的GNU标准C++库(libstdc++)与新版本操作系统之间的兼容性问题。在Linux环境中,Oracle数据库可能需要特定版本的...

Global site tag (gtag.js) - Google Analytics