URAL - 1297 Palindrome(后缀数组求最长回文子串)

2024-06-05 21:18

本文主要是介绍URAL - 1297 Palindrome(后缀数组求最长回文子串),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

The “U.S. Robots” HQ has just received a rather alarming anonymous letter. It states that the agent from the competing «Robots Unlimited» has infiltrated into “U.S. Robotics”. «U.S. Robots» security service would have already started an undercover operation to establish the agent’s identity, but, fortunately, the letter describes communication channel the agent uses. He will publish articles containing stolen data to the “Solaris” almanac. Obviously, he will obfuscate the data, so “Robots Unlimited” will have to use a special descrambler (“Robots Unlimited” part number NPRx8086, specifications are kept secret).
Having read the letter, the “U.S. Robots” president recalled having hired the “Robots Unlimited” ex-employee John Pupkin. President knows he can trust John, because John is still angry at being mistreated by “Robots Unlimited”. Unfortunately, he was fired just before his team has finished work on the NPRx8086 design.
So, the president has assigned the task of agent’s message interception to John. At first, John felt rather embarrassed, because revealing the hidden message isn’t any easier than finding a needle in a haystack. However, after he struggled the problem for a while, he remembered that the design of NPRx8086 was still incomplete. “Robots Unlimited” fired John when he was working on a specific module, the text direction detector. Nobody else could finish that module, so the descrambler will choose the text scanning direction at random. To ensure the correct descrambling of the message by NPRx8086, agent must encode the information in such a way that the resulting secret message reads the same both forwards and backwards. 
In addition, it is reasonable to assume that the agent will be sending a very long message, so John has simply to find the longest message satisfying the mentioned property.
Your task is to help John Pupkin by writing a program to find the secret message in the text of a given article. As NPRx8086 ignores white spaces and punctuation marks, John will remove them from the text before feeding it into the program.

Input

The input consists of a single line, which contains a string of Latin alphabet letters (no other characters will appear in the string). String length will not exceed 1000 characters.

Output

The longest substring with mentioned property. If there are several such strings you should output the first of them.

Sample Input

input output
ThesampletextthatcouldbereadedthesameinbothordersArozaupalanalapuazorA
ArozaupalanalapuazorA


题意:求最长回文子串。
思路:穷举每一位,然后计算以这个字符为中心的最长回文子串。注意这里要分两种情况,一是回文子串的长度为奇数,二是长度为偶数。两种情况都可以转化为求一个后缀和一个反过来写的后缀的最长公共前缀。具体的做法是:将整个字符串反过来写在原字符串后面,中间用一个特殊的字符隔开。这样就把问题变为求这个新的字符串的某两个后缀的最长公共前缀。然后在查找最长公共前缀lcp的时候利用到了RMQ,我们知道对于两个后缀j和k,设rank[j]<rank[k],则不难证明后缀j和k的LCP长度等于height[rank[j]+1],height[rank[j]+2],...,height[rank[k]]中的最小值,

即RMQ(height, rank[j]+1, rank[k]),这是通过height[]数组的两两比较做到的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 2010;int sa[maxn]; //SA数组,表示将S的n个后缀从小到大排序后把排好序的
//的后缀的开头位置顺次放入SA中
int t1[maxn], t2[maxn], c[maxn];
int rank[maxn], height[maxn];
int s[maxn], r[maxn];
char str[maxn];
int st[maxn][20];void build_sa(int s[], int n, int m) {int i, j, p, *x = t1, *y = t2;for (i = 0; i < m; i++) c[i] = 0;for (i = 0; i < n; i++) c[x[i] = s[i]]++;for (i = 1; i < m; i++) c[i] += c[i-1];for (i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;for (j = 1; j <= n; j <<= 1) {p = 0;for (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 < m; i++) c[i] = 0;for (i = 0; i < n; i++) c[x[y[i]]]++;for (i = 1; i < m; i++) c[i] += c[i-1];for (i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];swap(x, y);p = 1, x[sa[0]] = 0;for (i = 1; i < n; i++) x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+j] == y[sa[i]+j] ? p-1 : p++;if (p >= n) break;m = p;}
}void getHeight(int s[],int n) {int i, j, k = 0;for (i = 0; i <= n; i++)rank[sa[i]] = i;for (i = 0; i < n; i++) {if (k) k--;j = sa[rank[i]-1];while (s[i+k] == s[j+k]) k++;height[rank[i]] = k;}
}void ST(int n) {for (int i = 1; i <= n; i++)st[i][0] = i;for (int j = 1; (1<<j) <= n; j++) {for (int i = 1; i + (1<<j) <= n; i++) {int p = st[i][j-1];    int q = st[i+(1<<(j-1))][j-1];st[i][j] = height[p] > height[q] ? q : p;}}
}int RMQ(int i, int j) {int k = 0;if (i > j)swap(i, j);i++;while ((1<<(k+1)) <= j-i+1) k++;i = st[i][k];j = st[j-(1<<k)+1][k];return min(height[i], height[j]);
}int main() {while (scanf("%s", str) != EOF) {int len = strlen(str);int n = 2 * len + 1;for (int i = 0; i < len; i++)r[i] = str[i];r[len] = 1;for (int i = 0; i < len; i++)r[i+len+1] = str[len-1-i];r[n] = 0; //noticebuild_sa(r, n+1, 128);getHeight(r, n);ST(n);int mid = n >> 1;int ans = 0, cur = 0;for (int i = 0; i < mid; i++) {int j = RMQ(rank[i], rank[n-i-1]);  //奇对称if ((j<<1) - 1 > ans) { ans = (j<<1) - 1;cur = i - j + 1;}if (i) {j = RMQ(rank[i], rank[n-i]); //偶对称if ((j << 1) > ans) {ans = j << 1;cur = i - j;}}}for (int i = cur; i < cur + ans; i++)printf("%c", r[i]);printf("\n");}return 0;
}

这篇关于URAL - 1297 Palindrome(后缀数组求最长回文子串)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1034199

相关文章

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动