PALINY - Palindrome dài nhất
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
string s;
int manacher(const string &s) {
string t="^";
int c,r;
FORE(it,s) {
assert(*it!='^' && *it!='#' && *it!='$');
t.push_back('#');
t.push_back(*it);
}
t+="#$";
int n=t.size();
vector<int> p=vector<int>(n+7,0);
c=0;
r=0;
FOR(i,1,n-1) {
if (r>i) p[i]=min(r-i,p[2*c-i]);
else p[i]=0;
while (t[i+1+p[i]]==t[i-1-p[i]]) p[i]++;
if (i+p[i]>r) {
c=i;
r=i+p[i];
}
}
int ret=0;
FOR(i,1,n-1) ret=max(ret,p[i]);
return (ret);
}
int main(void) {
srand(time(NULL));
ios::sync_with_stdio(rand()%2);
cin >> s >> s;
cout << manacher(s);
return 0;
}