Pagini recente » Cod sursa (job #1792807) | Cod sursa (job #1141253) | Cod sursa (job #1487247) | Cod sursa (job #621890) | Cod sursa (job #1888362)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2000005
using namespace std;
char s[N], n;
long long v[N];
long long prelucrare()
{
long long c = 1, dr = 2;
v[0] = 0;
v[1] = 1;
for(long long i = 2 ; i <= 2 * n ; ++i)
{
if(i < dr)
{
v[i] = min(v[2 * c - i], dr - i);
}
while(i - v[i] - 1 >= 0 && i + v[i] + 1 <= 2 * n && s[i - v[i] - 1] == s[i + v[i] + 1])
{
v[i]++;
}
if(i + v[i] > dr)
{
dr = i + v[i];
c = i;
}
}
long long nr = 0;
for(long long i = 1 ; i <= 2 * n ; ++i)
{
if(v[i] % 2)
{
nr += (v[i] / 2 + 1);
}
else
{
nr += (v[i] / 2);
}
}
return nr;
}
void citire()
{
char tmp[1000005];
gets(tmp);
n = strlen(tmp);
for(int i = 0 ; i < n ; ++i)
{
s[2 * i] = '#';
s[2 * i + 1] = tmp[i];
}
s[2 * n] = '#';
printf("%lld",prelucrare());
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
citire();
return 0;
}