大致题意:
给出一个字符串,求出这个字符串中最长的回文串。如果有多个回文串的长度相等且都是最大,则输出最靠前的那个。
大致思路:
首先肯定是要把原字符的逆序串接到原字符串的后面。然后便是从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;
}
分享到:
相关推荐
后缀数组是字符串处理中的一种重要数据结构,它在计算机科学特别是文本算法领域扮演着关键角色。后缀数组能够提供一种高效的方式来存储和查询字符串的后缀,这使得它成为解决许多字符串问题的有效工具,例如查找模式...
4. **编辑距离**:后缀数组结合其他数据结构(如LCP数组和RMQ(Range Minimum Query))可以快速计算两个字符串的编辑距离。 5. **AC自动机**:后缀数组是构建AC自动机的基础,用于支持多个模式的并行匹配。 ### ...
本文将深入探讨后缀数组及其相关概念,包括SA(Suffix Array)、Height、RMQ(Range Minimum Query)以及多串匹配。 首先,让我们理解什么是后缀数组(Suffix Array)。后缀数组是字符串的所有后缀按字典序排序后的...
在字符串处理的背景下,后缀数组的k-前缀比较关系、名次数组Rank、基数排序、以及最长公共前缀的RMQ问题都是需要掌握的关键知识点。名次数组Rank实际上是后缀数组的辅助数据结构,用于快速查询某个后缀在排序后的...
根据给定的信息,本文将详细解释“后缀数组C++实现代码”中涉及的重要知识点,包括后缀数组、倍增算法、以及RMQ(Range Minimum Query)问题。 ### 一、后缀数组 #### 1.1 定义 后缀数组是一种数据结构,它存储了...
关键词包括:字符串、后缀、k-前缀比较关系、后缀数组、名次数组、后缀树、倍增算法、基数排序、最长公共前缀、RMQ问题、模式匹配、回文串和最长回文子串。 总的来说,后缀数组是字符串处理中的重要工具,它提供了...
结合这两个知识点,我们可以构建一个系统,先用倍增算法构建后缀数组,然后利用ST算法实现的RMQ功能来快速查询字符串中某段后缀的最小值,这对于分析字符串性质或者进行特定的字符串搜索任务非常有用。在实际应用中...
给定一个数组`A[1...n]`,对于任意的两个索引`i`和`j` (`i ≤ j`),RMQ问题的目标是在`A[i...j]`区间内找到最小值的位置或最小值本身。这是一个非常基础但又非常实用的问题,在许多动态规划和数据结构问题中都有应用...
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 Array)详解 #### 引言 后缀数组是计算机科学领域内一种高效的数据结构,主要用于字符串处理,特别是模式匹配、文本分析等场景。它能够快速定位一个子串在主串中的位置,对于解决复杂的字符...
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)....
此外,代码中还提到了RMQ(Range Minimum Query,区间最小值查询)版本的后缀数组,这表明可能在处理后缀数组时,也考虑了区间内的最小值查询问题,这对于某些特定的应用场景非常有效。 总结起来,后缀数组是字符串...
- **后缀数组**:构建后缀数组,并计算height数组。 - **最长回文子串预处理**:预处理以每个位置为中心的最长回文子串。 - **结构体数组**:构造一个结构体数组存储每个回文子串的左边界和中心位置,并按左边界排序...
RMQ 动画 这是用于创建文档中说明的动画的应用程序。 这个 repo 是一个简单的应用程序,用于说明 RMQ 可用的动画: rmq(my_view).animations.fade_in rmq(my_view).animations.fade_out rmq(my_view).animations....
12. **后缀数组**:后缀数组是字符串处理中的一种数据结构,用于快速访问字符串的所有后缀,常用于模式匹配和文本分析。 13. **归并树**:归并树(Merge Sort Tree)是基于归并排序构建的数据结构,用于高效地处理...
ACM算法讲解 本文将对ACM主要算法进行讲解,涵盖了基本算法、图算法、数据结构、搜索、计算几何学、动态规划和综合题等多方面的知识点。 一、基本算法 ... + 后缀数组、后缀树 + 块状链表 + 哈夫曼树
在处理字符串问题时,RMQ算法有时能与其他数据结构(如后缀数组、线段树等)结合,提供高效的解决方案。 总结起来,掌握字符串哈希和后缀数组是提升在字符串处理领域技能的关键。通过学习哈希,我们可以快速比较...
RMQ.io 您是否要构建可靠且易于编码的连接服务?Rmq.io的任务rmq.io的任务是使RabbitMQ的发布订阅变得容易1,2,3基本原理一个可靠且简单的pubsub并不容易找到。 RabbitMQ是功能强大的消息队列,它具有许多功能,对于...
`compat-libstdc.rpm` 文件是Oracle数据库安装过程中经常遇到的一个依赖组件,它主要用于解决旧版本的GNU标准C++库(libstdc++)与新版本操作系统之间的兼容性问题。在Linux环境中,Oracle数据库可能需要特定版本的...