Pagini recente » Cod sursa (job #1811808) | Cod sursa (job #743432) | Cod sursa (job #2154664) | Cod sursa (job #1632776) | Cod sursa (job #2664969)
#include <iostream>
#include <fstream>
#define NMAX 1000000
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
long long n, v[2*NMAX+10], ans;
char s[2*NMAX+10];
string s1;
int main()
{
f >> s1;
int n1 = s1.size();
s[++n] = '%';
s[++n] = '#';
for(int i=0; i<n1; i++)
{ s[++n] = s1[i];
s[++n] = '#';
}
s[++n] = '$';
int C = 0, R = 0;
for(int i=1; i<n; i++)
{ int ogl = 2 * C - i;
if(i < R) v[i] = min((long long)(R - i), v[ogl]);
while(s[i+v[i]+1] == s[i-v[i]-1]) v[i]++;
if(i + v[i] > R)
{ C = i;
R = v[i] + i;
}
}
for(int i=0; i<n; i++) ans = ans + (v[i] + 1) / 2;
g << ans << '\n';
return 0;
}