Pagini recente » Cod sursa (job #1011853) | Cod sursa (job #1442764) | Cod sursa (job #1179976) | Statistici Marin Vasile Peptenaru (MarinPeptenaru) | Cod sursa (job #667589)
Cod sursa(job #667589)
#include <cstdio>
#include<algorithm>
#define infile "pscpld.in"
#define outfile "pscpld.out"
#define n_max 2000005
using namespace std;
char S[n_max];
int Lung[n_max];
int N;
long long sol;
void citeste()
{
freopen(infile,"r",stdin);
do
{
N++;
scanf("%c",&S[2*N-1]);
}while(S[2*N-1]);
N--;
fclose(stdin);
}
void rezolva()
{
int idx = 1;
for (int i=1; i<2*N; ++i)
{
if (idx + Lung[idx] - 1 < i)
Lung[i] = i&1;
else
Lung[i] = min(Lung[idx - (i - idx)], idx + Lung[idx] - i );
int j = Lung[i] + 1;
while (i - j >= 1 && i + j < 2*N && S[i-j] == S[i+j])
j+=2;
j -= 2;
Lung[i] = j + 1;
if ( i + Lung[i] > idx + Lung[idx])
idx = i;
sol += (Lung[i] + 1) / 2;
}
}
void afiseaza()
{
freopen(outfile,"w",stdout);
printf("%lld\n",sol);
fclose(stdout);
}
int main(void)
{
citeste();
rezolva();
afiseaza();
return 0;
}