Pagini recente » Cod sursa (job #1535845) | Cod sursa (job #1968912) | Cod sursa (job #636758) | Cod sursa (job #1990119) | Cod sursa (job #667660)
Cod sursa(job #667660)
#include <cstdio>
#include<algorithm>
#define infile "pscpld.in"
#define outfile "pscpld.out"
#define n_max 2000005
using namespace std;
char S[n_max];
int Lg[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 + Lg[idx] - 1 < i)
Lg[i] = i&1;
else
Lg[i] = min(Lg[idx - (i - idx)], idx + Lg[idx] - i);
int j = Lg[i] + 1;
while (i - j >= 1 && i + j < 2 * N && S[i - j] == S[i + j])
j += 2;
j -= 2;
Lg[i] = j + 1;
if (i + Lg[i] > idx + Lg[idx])
idx = i;
sol += (Lg[i] + 1) / 2;
}
}
void afiseaza()
{
freopen(outfile,"w",stdout);
printf("%lld\n",sol);
fclose(stdout);
}
int main(void)
{
citeste();
rezolva();
afiseaza();
return 0;
}