Solution Extend to Palindrome
题目大意：给定一个字符串(S)，你需要求字符串(S^*)，满足(S)是(S^*)的前缀，(S^*)是个回文子串，在这前提下使得(S^*)长度尽量小
(Manacher)，贪心
分析：
既然(S)是(S^*)的前缀，那么(S^*)可以看做由(S)末尾追加一个字符串得来，我们要使得这个追加字符串的长度尽量小
由于回文串的性质，追加字符串对应(S^*)的前缀，我们要使追加字符串长度尽量小就要使得这个前缀的长度尽量小，于是我们在(S)中找是(S)的后缀的最长回文子串即可
然后就是(Manacher)板子了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 100;
char org[maxn],str[maxn],ans[maxn];
int len[maxn],n,siz;
inline void init(){
str[siz = 0] = '$';
for(int i = 1;i <= n;i++)
str[++siz] = '#',str[++siz] = org[i];
str[++siz] = '#';
str[siz + 1] = '?';
}
inline void manacher(){
int pos = 0,mx = 0;
for(int i = 1;i <= siz;i++){
if(i < mx)len[i] = min(mx - i,len[2 * pos - i]);
else len[i] = 1;
while(str[i - len[i]] == str[i + len[i]])len[i]++;
if(i + len[i] > mx){
mx = i + len[i];
pos = i;
}
}
}
inline void solve(){
n = strlen(org + 1);
init();
manacher();
int i;
for(i = 1;i <= siz && i + len[i] - 1 != siz;i++);
memcpy(ans,str,sizeof(char) * (siz + 1));
ans[0] = ' ';
for(int delta = 0;i - delta >= 0;delta++)
ans[i + delta] = ans[i - delta];
for(i = 1;ans[i] != ' ';i++)
if(ans[i] != '#')putchar(ans[i]);
putchar('
');
}
int main(){
while(~scanf("%s",org + 1))solve();
return 0;
}