Pagini recente » Cod sursa (job #1593932) | Cod sursa (job #2018610) | Cod sursa (job #369312) | Cod sursa (job #2326526) | Cod sursa (job #1050204)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#define get_min(a,b) ((a)<(b)?(a):(b))
#define MAX_SIZE 1000005
using namespace std;
ifstream in ( "pscpld.in" );
ofstream out ( "pscpld.out" );
char sir[MAX_SIZE];
int DP[2][MAX_SIZE] , N ;
long long Sol ;
int Expand ( int Left , int Right )
{
int len = 0 ;
for ( ;Left > 0 and Right <= N and sir[Left] == sir[Right]; ++len , ++Right , --Left );
return len;
}
void ManacherUnEven ( void )
{
int i , j , P = 0 , R = 0;
for ( i = 1 ; i <= N ; ++i )
{
int Left , Right ;
if ( R >= i )
{
DP[0][i] = get_min ( DP[0][ P - ( i-P) ] , R -i );
}
Left = i - DP[0][i];
Right = i + DP[0][i];
DP[0][i] = Expand ( Left , Right );
if ( i + DP[0][i] > R )
{
P = i ;
R = i + DP[0][i];
}
Sol += ( long long) DP[0][i];
}
}
void ManacherEven ( void )
{
int i , j , P = 0 , R = 0;
for ( i = 1 ; i <= N ; ++i )
{
int Left , Right ;
if ( sir[i] != sir[i+1] ) continue;
if ( R > i )
{
DP[1][i] = get_min ( DP[1][ P - ( i-P) ] , R -i -1 );
}
Left = i - DP[1][i];
Right = i + DP[1][i];
DP[1][i] = Expand ( Left , Right );
if ( i + 1 + DP[1][i] > R )
{
P = i ;
R = i + 1 + DP[1][i];
}
Sol += ( long long) DP[1][i];
}
}
int main ( void )
{
in >> ( sir + 1 );
sir[0] = ' ';
N = strlen(sir) - 1;
ManacherEven();
ManacherUnEven();
out << Sol << "\n";
in.close();
out.close();
return 0;
}