Pagini recente » Cod sursa (job #2875874) | Cod sursa (job #821381) | Cod sursa (job #2158584) | Cod sursa (job #1234052) | Cod sursa (job #2192126)
#include <fstream>
#include <cstring>
#define Nmax 3000005
using namespace std;
ifstream f ("pscpld.in");
ofstream g ("pscpld.out");
int man[Nmax];
char a[Nmax], x;
long long ans, len;
void read()
{ a[0]='#';
while ( f >> x )
{
a[++len]=x;
a[++len]='#';
}
len--;
}
void manachers()
{
int mid=1, rgt=1;
man[1]=1;
for ( int i = 1 ; i <= len ; i ++ )
{
if(i<=rgt)
man[i]=min(rgt-i, man[2*mid-i]);
while ( (a[i+man[i]]==a[i-man[i]]) && (i-man[i]>0) && (i+man[i]<=len) )
man[i]++;
if ( i+man[i] > rgt )
{
mid=i;
rgt=i+man[i];
}
}
}
void solve()
{
for ( int i = 1 ; i <= len ; i ++ )
{
man[i]--;
man[i]=man[i]/2;
if(i%2==1)
ans++;
ans+=1LL*man[i];
}
g << ans;
}
int main()
{
read();
manachers();
solve();
return 0;
}