Pagini recente » Cod sursa (job #1998165) | Cod sursa (job #1873403) | Cod sursa (job #1594858) | Cod sursa (job #1086331) | Cod sursa (job #1444323)
/*
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 = 100010;
int n , i , lg , sol , right , C;
int max_expand[Nmax];
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 += (max_expand[i] + 1) / 2;
if (i + max_expand[i] > right)
C = i, right = i + max_expand[i];
}
printf("%d\n", sol);
return 0;
}