1297. Palindrome
Memory Limit: 16 MB
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.
Input
Output
Sample
| input |
|---|
ThesampletextthatcouldbereadedthesameinbothordersArozaupalanalapuazorA |
| output |
ArozaupalanalapuazorA |
Mean:
给你一个字符串，让你输出字符串的最长回文子串。
analyse:
求最长回文串有很多方法，最经典的莫过于Manacher算法，时间复杂度O(n)。
这里就主要介绍一下用后缀数组的方法。
用后缀数组怎么求回文串呢？
原理和上一篇求最长公共子序列一样，我们把s1反转后接到s1后面得到S串，那么s1的最长回文串必定存在于S中，我们只需要求一下S的height数组，然后寻找来自于不同的两个串的height[i]的最大值，然后记录一下开始位置和长度，最后输出即可。
Time complexity：O(nlogn)
Source code：
Suffix Arrays:
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-05-09-21.22
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXN=;
//以下为倍增算法求后缀数组
int wa[MAXN],wb[MAXN],wv[MAXN],Ws[MAXN];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
/**< 传入参数：str,sa,len+1,ASCII_MAX+1 */
void da(const char *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=; i<m; i++) Ws[i]=;
for(i=; i<n; i++) Ws[x[i]=r[i]]++;
for(i=; i<m; i++) Ws[i]+=Ws[i-];
for(i=n-; i>=; i--) sa[--Ws[x[i]]]=i;
for(j=,p=; p<n; j*=,m=p)
{
for(p=,i=n-j; i<n; i++) y[p++]=i;
for(i=; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=; i<n; i++) wv[i]=x[y[i]];
for(i=; i<m; i++) Ws[i]=;
for(i=; i<n; i++) Ws[wv[i]]++;
for(i=; i<m; i++) Ws[i]+=Ws[i-];
for(i=n-; i>=; i--) sa[--Ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=,x[sa[]]=,i=; i<n; i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
}
return;
}
int sa[MAXN],Rank[MAXN],height[MAXN];
/**< str,sa,len */
void calheight(const char *r,int *sa,int n)
{
int i,j,k=;
for(i=; i<=n; i++) Rank[sa[i]]=i;
for(i=; i<n; height[Rank[i++]]=k)
for(k?k--:,j=sa[Rank[i]-]; r[i+k]==r[j+k]; k++);
// Unified
for(int i=n;i>=;--i) ++sa[i],Rank[i]=Rank[i-];
}
char s1[MAXN],s2[MAXN];
int main()
{
while(~scanf("%s",s1))
{
int l1=strlen(s1);
strcat(s1,"{");
strcpy(s2,s1);
for(int i=;i<l1;++i) s1[i+l1+]=s2[l1-i-];
int len=strlen(s1);
da(s1,sa,len+,);
calheight(s1,sa,len);
int sta=,maxLen=,l,r;
for(int i=;i<=len;++i)
{
l=min(sa[i]-,sa[i-]-);
r=max(sa[i]-,sa[i-]-);
if((l<l1&&r>l1) && (len-r==l+height[i]))
{
if(height[i]>maxLen)
maxLen=height[i],sta=l;
else if(height[i]==maxLen)
sta=min(sta,l);
}
}
for(int i=sta,j=;j<maxLen;++i,++j)
printf("%c",s1[i]);
puts("");
}
return ;
}
Manacher：
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-09-12-15.41
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define max(a,b) (a>b?a:b)
using namespace std;
typedef long long(LL);
typedef unsigned long long(ULL);
const double eps(1e-8);
/** O(n)内求出所有回文串
*原串 :abaaba
*Ma串 :.,a,b,a,a,b,a,
*Mp[i]:Ma串中，以字符Ma[i]为中心的最长回文子串的半径长度(包括Ma[i],也就是把回文串对折后的长度).
****经过对原串扩展处理后，将奇数串的情况也合并到了偶数的情况(不需要考虑奇数串)
*/
const int MAXN=;
char Ma[MAXN*],s[MAXN];
int Mp[MAXN*],Mplen;
void Manacher(char s[],int len)
{
int le=;
Ma[le++]='.';
Ma[le++]=',';
for(int i=;i<len;++i)
{
Ma[le++]=s[i];
Ma[le++]=',';
}
Mplen=le;
Ma[le]=;
int pnow=,pid=;
for(int i=;i<le;++i)
{
if(pnow>i)
Mp[i]=min(Mp[*pid-i],pnow-i);
else
Mp[i]=;
for(;Ma[i-Mp[i]]==Ma[i+Mp[i]];++Mp[i]);
if(i+Mp[i]>pnow)
{
pnow=i+Mp[i];
pid=i;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie();
while(~scanf("%s",s))
{
Manacher(s,strlen(s));
int maxLen=,idx=;
for(int i=;i<Mplen;++i)
{
if(Mp[i]>maxLen)
maxLen=Mp[i],idx=i;
}
for(int i=(idx-maxLen+)/,j=;j<maxLen-;++i,++j)
printf("%c",s[i]);
puts("");
// cout<<maxLen-1<<endl;
}
return ;
}