Pagini recente » Cod sursa (job #395578) | Cod sursa (job #638941) | Cod sursa (job #336530) | Cod sursa (job #2211863) | Cod sursa (job #2261486)
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
char c[1000010], s[2000010];
int i,j,n,m,k,p,best[2000010],bst,ans,sim;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int expand( int poz , int off = 0 ){
int i,j;
for( i = poz - off , j = poz + off ; i >= 0 && j < n ; j++ , i-- ){
if( s[ i ] != s[ j ] )
break;
}
return j - poz;
}
int main(){
fin.get( c , 1000010 );
n = strlen( c );
for( int i = 0 ; i < n ; i++ ){
s[ 2 * i ] = '*';
s[ 2 * i + 1 ] = c[ i ];
}
n = 2 * n;
best[0] = 1;
bst = 0;
//cout<<"* 1\n";
for( int i = 1 ; i < n ; i++ ){
//cout << bst << ' ' << best[ bst ] << '\n';
if( i >= bst + best[ bst ] ){
bst = i;
best[ i ] = expand( i );
} else {
int sim = bst - ( i - bst );
best[ i ] = min( best[ sim ] , bst + best[ bst ] - i );
best[ i ] = expand( i , best[ i ] - 1 );
}
ans = ans + ( best[ i ] + 1 ) / 2;
//cout << s[ i ] << ' ' << ' ' << ' ' << best[ i ] << '\n';
}
fout << ans - n / 2 + 1;
return 0;
}