Pagini recente » Cod sursa (job #412835) | Cod sursa (job #2833833) | Cod sursa (job #1295208) | Cod sursa (job #622275) | Cod sursa (job #1444325)
/*
If you can't explain it simply, you don't understand it well enough.
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int Nmax = 1000010;
int n , i , lg , right , C;
int max_expand[2*Nmax];
long long sol;
char aux[Nmax] , sir[2*Nmax];
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
gets(aux + 1); n = strlen(aux + 1);
sir[lg] = '$'; sir[++lg] = '#';
for (i = 1; i <= n; ++i)
{
sir[++lg] = aux[i];
sir[++lg] = '#';
}
sir[lg+1] = '*';
for (i = 1; i <= lg; ++i)
{
int simetric_C = C - (i - C);
max_expand[i] = (right > i) ? min(max_expand[simetric_C] , right - i) : 0;
while (sir[i+max_expand[i]+1] == sir[i-max_expand[i]-1])
max_expand[i]++;
sol += 1LL * (max_expand[i] + 1) >> 1;
if (i + max_expand[i] > right)
C = i, right = i + max_expand[i];
}
printf("%lld\n", sol);
return 0;
}