Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Istoria paginii utilizator/ruxandrasofronie | Istoria paginii utilizator/nikomiu95 | Cod sursa (job #2016418)
#include<fstream>
#include<cstring>
#define DIM 2000005
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int n, Long_pal[DIM], poz, R, C;
long long sol = 0;
char s[DIM / 2], v[DIM];
int main(){
fin >> s + 1;
n = strlen( s + 1 );
n = n * 2 + 1;
poz = 1;
for( int i = 1; i <= n; i++ ){
if( i % 2 == 0 )
v[i] = s[poz++];
else
v[i] = '#';
}
v[0] = '0';
v[n + 1] = '1';
C = R = 0;
for( int i = 1; i <= n; i++ ){
int mirr_poz = 2 * C - i;
if( i < R )
Long_pal[i] = min( R - i, Long_pal[mirr_poz] );
while( v[ i - Long_pal[i] - 1 ] == v[ i + Long_pal[i] + 1 ] )
Long_pal[i]++;
if( i + Long_pal[i] > R ){
R = i + Long_pal[i];
C = i;
}
sol += (Long_pal[i] + 1) / 2;
}
fout << sol << "\n";
return 0;
}