Pagini recente » Cod sursa (job #1094197) | Cod sursa (job #885643) | Cod sursa (job #594299) | Cod sursa (job #42533) | Cod sursa (job #997067)
Cod sursa(job #997067)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int Nmax = 1000005;
int N;
char s[Nmax], sir[2 * Nmax];
int P[2 * Nmax];
void read()
{
ifstream f("pscpld.in");
f.getline( s, Nmax );
sir[ ++N ] = '#';
for ( int i = 0; s[i] != '\0'; ++i )
{
sir[ ++N ] = s[i];
sir[ ++N ] = '#';
}
f.close();
}
void Manacher()
{
ofstream g("pscpld.out");
int mx = 0, ind = 0, sol = 0;
for ( int i = 1; i <= N; ++i )
{
if ( mx >= i )
{
P[i] = min( mx - i, P[2 * ind - 1] );
}
while ( i - P[i] >= 1 && i + P[i] < N && sir[i - P[i]-1] == sir[i + P[i] + 1] )
P[i]++;
if ( i + P[i] > mx )
{
mx = i + P[i];
ind = i;
}
}
for ( int i = 1; i <= N; ++i )
sol += ( P[i] + 1 ) / 2;
g<<sol;
}
int main()
{
read();
Manacher();
return 0;
}