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

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

ural 1297. Palindrome dp

1297. Palindrome Time limit: 1.0 second Memory limit: 64 MB The “U.S. Robots” HQ has just received a rather alarming anonymous letter. It states that the agent from the competing «Robots Unli