Pagini recente » Cod sursa (job #1543768) | Cod sursa (job #140755) | Cod sursa (job #2672637) | Cod sursa (job #2321979) | Cod sursa (job #2723112)
#include <iostream>
#include <fstream>
#include <cstring>
#define ll long long
#define NMAX 1000000
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char s[NMAX+10], t[2*NMAX+10];
ll ans;
int k, v[2*NMAX+10];
int main()
{
fin >> s;
t[++k] = '&';
t[++k] = '#';
int n = strlen(s);
for(int i=0; i<n; i++)
{ t[++k] = s[i];
t[++k] = '#';
}
t[++k] = '%';
int C = 0, R = 0;
for(int i=1; i<k; i++)
{ int ogl = 2 * C - i;
if(i < R) v[i] = min(R - i, v[ogl]);
while(t[i+v[i]+1] == t[i-v[i]-1])
v[i]++;
if(i + v[i] > R)
{ C = i;
R = i + v[i];
}
}
for(int i=0; i<k; i++)
ans = ans + ((ll)v[i] + 1) / 2;
fout << ans << '\n';
return 0;
}