Prefix-Suffix Palindrome

Link: Prefix-Suffix Palindrome

Description

You are given a string s, consisting of lowercase English letters. Find the longest string, t, which satisfies the following conditions:

  • The length of t does not exceed the length of s.
  • t is a palindrome.
  • There exists two strings a and b (possibly empty), such that t=a+b ( "+" represents concatenation), and a is prefix of s while b is suffix of s.

Input
The input consists of multiple test cases. The first line contains a single integer t (), the number of test cases. The next t lines each describe a test case.

Each test case is a non-empty string s, consisting of lowercase English letters.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed .

Output
For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.

Example
input
5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba
output
a
abcdfdcba
xyzyx
c
abba
Note
In the first test, the string s="a" satisfies all conditions.

In the second test, the string "abcdfdcba" satisfies all conditions, because:

  • Its length is 9, which does not exceed the length of the string s, which equals 11.
  • It is a palindrome.
  • "abcdfdcba" = "abcdfdc" + "ba", and "abcdfdc" is a prefix of s while "ba" is a suffix of s.
    It can be proven that there does not exist a longer string which satisfies the conditions.

In the fourth test, the string "c" is correct, because "c" = "c" + "" and a or b can be empty. The other possible solution for this test is "s".

Problem solving

这道题的意思就是给你一个字符串,你可以选择一个字符串的前缀子串和一个后缀子串,使得两个字串合起来是回文串.并且另回文串尽可能地长.换句话说就是你可以删去一个子串,使得字符串剩下的部分为回文串.求最长的可以剩下的回文串.

首先我们可以求出字符串两边可以构造出的回文串,假设字符串的,我们比较和,如果相等就继续比较否则退出循环.剩下的最长的回文子串一定包含两边可以构造出来的回文串.因为你要选的是前缀,后缀合起来.
这个统计完之后,把已经构成了回文串的字符不再考虑,我们考虑剩下的子串中前缀和后缀中的最长回文子串,选长的那个,加上上一步我们得到的回文串.就是最后的答案.求最长回文子串可以用马拉车,这里我用了哈希.
不过哈希里面的和一定要选好.这里挺好用的一组就是.单哈希不行就双哈希,爱了爱了,复杂度为

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll base = 233;
const int maxn = 1e6+10;
const int mod = 1e9+7;
ll p[maxn],l[maxn],r[maxn];
bool check(ll L,ll R){
    ll x,y;
    x=(l[R]-l[L-1]*p[R-L+1]%mod+mod)%mod;
    y=(r[L]-r[R+1]*p[R-L+1]%mod+mod)%mod;//求子串的哈希值,模板
    return x==y;//如果前缀和后缀哈希值相等,说明这个子串是回文串
}
int main()
{
    ios::sync_with_stdio(0);
    p[0]=1;
    ll t;
    cin>>t;
    while(t--)
    {    
        string s;
        cin>>s;
        ll n=s.size();
        s=" "+s;//把字符串中的字符下标置为1-n,方便处理
        for(ll i=1;i<=n;i++)    l[i]=l[i-1]*base%mod+s[i],p[i]=p[i-1]*base,l[i]%=mod,p[i]%=mod;//计算前缀哈希值,p[i]为base的i次方,优化时间
        for(ll i=n;i>=1;i--)    r[i]=r[i+1]*base%mod+s[i],r[i]%=mod;//计算后缀哈希值
        ll pos=0;
        for(ll i=1;i<=n/2;i++){
            if(s[i]==s[n+1-i]){
                pos=i;
            }
            else    break;
        }//找到原字符串前后可以构建出的最长回文子串
        ll flag=0,maxx=0;
        for(ll i=pos+1;i<=n-pos;i++){
            if(check(pos+1,i)&&i-pos>maxx){
                flag=1;
                maxx=i-pos;
            }
        }//求剩下的字符串前缀最长回文子串
        for(ll i=n-pos;i>=pos+1;i--){
            if(check(i,n-pos)&&n-pos-i+1>maxx){
                flag=2;
                maxx=n-pos-i+1;
            }
        }//求剩下的字符串后缀最长回文子串
        /*然后输出即可*/
        for(ll i=1;i<=pos;i++)    cout<<s[i];
        if(flag==1){
            for(ll i=pos+1;i<=pos+maxx;i++)    cout<<s[i];
        }else if(flag==2){
            for(ll i=n-pos-maxx+1;i<=n-pos;i++)    cout<<s[i];
        }
        for(ll i=n-pos+1;i<=n;i++)    cout<<s[i];
        cout<<endl;
    }
    return 0;
}
赏