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