Pagini recente » Cod sursa (job #1195834) | Cod sursa (job #2665164) | Cod sursa (job #1266325) | Cod sursa (job #1185310) | Cod sursa (job #1311820)
#include <fstream>
#include <string>
#include <cstring>
using namespace std;
const int NMAX= 1000000;
ifstream in( "pscpld.in" );
ofstream out( "pscpld.out" );
string s, v;
int d[NMAX*2+2], c;
int main( )
{
in >> s;
int N= s.size();
for ( int i= 0; i<N; ++i )
{
v+= '$';
v+= s[i];
}
v+= '$';
N= v.size();
for ( int i= 0; i<N; ++i )
{
int aux= 0;
if ( c+d[c]>=i )
{
aux= min( d[2*c-i], c+d[c]-i );
}
while ( i-aux-1>=0 && i+aux+1<N && v[i-aux-1]==v[i+aux+1] )
{
++aux;
}
d[i]= aux;
if ( c+d[c]<i+d[i] )
{
c= i;
}
}
long long ans= N/2;
for ( int i= 0; i<N; ++i )
{
ans+= d[i]/2;
}
out << ans << '\n';
return 0;
}