CF1326D2 Prefix-Suffix Palindrome (Hard version)
给你一个由小写英文字母组成的字符串 \(s\) 。请找出满足以下条件的最长字符串 \(t\) ：
- \(t\) 的长度不超过 \(s\) 的长度。
- \(t\) 是一个回文字符串。
- 存在两个字符串 \(a\) 和 \(b\) （可能为空），使得 \(t = a + b\) （" \(+\) "表示连接）和 \(a\) 是 \(s\) 的前缀，而 \(b\) 是 \(s\) 的后缀。
这里KMP用于计算最长前缀最长回文串的长度。若是要计算最长后缀回文串的长度，只需将原字符串反转，然后计算反转后字符串的前缀最长回文串的长度即可。
具体方法：构造字符串\(S+\#+S'\)（其中\(S'\)表示字符串\(S\)的反转），然后计算前缀数组即可，最后一个元素的前缀数组值即为最长前缀最长回文串的长度。
原理：回文串的定义和前缀数组的定义。
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define mid (((l)+(r))/2)
#define sq(x) ((x)*(x))
#define cu(x) ((x)*(x)*(x))
using namespace std;
typedef long long ll;
typedef long double ld;
const ll N=1e6+10,inf=1e18+10,mod=1e9+7;
ll n,m,kmp[N<<1];
char s[N],t[N<<1];
ll work(){
for(ll i=2,j=0;i<=m;i++){
while(j&&t[i]!=t[j+1])j=kmp[j];
kmp[i]=j+=t[i]==t[j+1];
}
return kmp[m];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--){
cin >> (s+1);
n=strlen(s+1);
ll l=0,r=n+1;
while(s[l+1]==s[r-1]&&l+1<r-1)l++,r--;
for(ll i=l+1,m=0;i<=r-1;i++)t[++m]=s[i];
t[++m]='#';
for(ll i=r-1;i>=l+1;i--)t[++m]=s[i];
ll lenl=work();
for(ll i=r-1,m=0;i>=l+1;i--)t[++m]=s[i];
t[++m]='#';
for(ll i=l+1;i<=r-1;i++)t[++m]=s[i];
ll lenr=work();
for(ll i=1;i<=l;i++)cout << s[i];
if(lenl>lenr)for(ll i=l+1;i<=l+lenl;i++)cout << s[i];
else for(ll i=r-lenr;i<=r-1;i++)cout << s[i];
for(ll i=r;i<=n;i++)cout << s[i];
cout << endl;
}
return 0;
}