Pagini recente » Cod sursa (job #3216902) | Cod sursa (job #2389865) | Cod sursa (job #1084361) | Cod sursa (job #3181578) | Cod sursa (job #2737910)
#include <bits/stdc++.h>
using namespace std;
const int NMAX(2000005);
char sir[NMAX], sir2[NMAX];
int pal[NMAX];
int main()
{
ios_base::sync_with_stdio(false);
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
cin.getline(sir + 1, NMAX - 3);
int lg = strlen(sir + 1);
int n = 0;
sir2[++n] = '#';
for(int i = 1; i <= lg; ++i)
sir2[++n] = sir[i], sir2[++n] = '#';
pal[1] = 1;
int c = 1, dr = 1;
long long rez = 0;
for(int i = 2; i <= n; ++i){
int lg = 0;
if(i <= dr)
lg = min(pal[2 * c - 1], dr - i + 1);
while(i - lg > 0 && i + lg <= n && sir2[i + lg] == sir2[i - lg])
++lg;
if(i + lg - 1 > dr){
dr = i + lg - 1;
c = i;
}
pal[i] = lg;
if(i % 2 == 0)
rez += (lg + 1) / 2;
else rez += lg / 2;
}
cout << rez << '\n';
return 0;
}