Pagini recente » Cod sursa (job #2618702) | Cod sursa (job #2891416) | Cod sursa (job #2895710) | Cod sursa (job #3040427) | Cod sursa (job #2847309)
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
ifstream fin( "pscpld.in" );
ofstream fout( "pscpld.out" );
const int MAXN = 1000005;
string transform( const string &s );
int ext[2 * MAXN + 1];
string s, t;
void Manacher( const string &s ) {
t = transform(s);
int l = 0, r = 0, n = t.length();
ext[0] = 1;
for ( int i = 1; i < n; i++ ) {
if ( i <= r ) {
ext[i] = min( r - i + 1, ext[l + (r - i)] );
}
while ( i + ext[i] < n && i - ext[i] >= 0 && t[i - ext[i]] == t[i + ext[i]] ) {
++ext[i];
}
if ( i + ext[i] - 1 > r ) {
l = i - ext[i] + 1;
r = i + ext[i] - 1;
}
}
}
int main() {
long long res = 0;
fin >> s;
Manacher(s);
for ( int i = 0; i < t.length(); ++i ) {
res += ext[i] / 2;
}
fout << res;
fin.close();
fout.close();
return 0;
}
string transform( const string &s ) {
string st;
st.push_back('#');
for ( auto ch : s ) {
st.push_back(ch);
st.push_back('#');
}
return st;
}