Pagini recente » Cod sursa (job #1629116) | Cod sursa (job #2701538) | Cod sursa (job #2042386) | Cod sursa (job #1014305) | Cod sursa (job #2737908)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int NMAX(2000005);
char sir[NMAX], sir2[NMAX];
int pal[NMAX];
int main()
{
fin.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;
}
fout << rez << '\n';
return 0;
}