Pagini recente » Cod sursa (job #757091) | Cod sursa (job #1620138) | Cod sursa (job #134551) | Cod sursa (job #677639) | Cod sursa (job #2192114)
#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 ++ )
{
man[i]=min(rgt-i+1, man[2*mid-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]/2+i%2;
ans+=man[i];
}
g << ans;
}
int main()
{
read();
manachers();
solve();
return 0;
}