Pagini recente » Cod sursa (job #2248457) | Cod sursa (job #43773) | Cod sursa (job #1709457) | Cod sursa (job #1157394) | Cod sursa (job #1003851)
#include<cstdio>
#include<cstring>
using namespace std;
int pozmax1[1000005], pozmax2[1000005];
char sir[1000005];
int maxim(int a, int b)
{
if(a < b)
return b;
else
return a;
}
int minim(int a, int b)
{
if(a > b)
return b;
else
return a;
}
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
int n, i, pozdi1 = 0, pozdi2 = 0;
long long s = 0;
gets(sir);
n = strlen(sir);
for(i = 1; i <= n; ++ i)
{
pozmax1[i] = 0;
if(pozdi1 + pozmax1[pozdi1] >= i)
pozmax1[i] = maxim(pozmax1[i], minim(pozmax1[pozdi1 + pozdi1 - i], pozdi1 + pozmax1[pozdi1] - i));
while(i - pozmax1[i] >= 2 && i + pozmax1[i] + 1 <= n && sir[i - pozmax1[i] - 2] == sir[i + pozmax1[i]])
{
++ pozmax1[i];
}
if(i + pozmax1[i] > pozdi1 + pozmax1[pozdi1])
pozdi1 = i;
s += pozmax1[i] + 1;
pozmax2[i] = 0;
if(pozdi2 + pozmax2[pozdi2] >= i + 1)
pozmax2[i] = maxim(pozmax2[i], minim(pozmax2[pozdi2 + pozdi2 - i], pozdi2 + pozmax2[pozdi2] - i));
while(i - pozmax2[i] >= 1 && i + pozmax2[i] + 1 <= n && sir[i - pozmax2[i] - 1] == sir[i + pozmax2[i]])
{
++ pozmax2[i];
}
if(i + pozmax2[i] > pozdi2 + pozmax2[pozdi2])
pozdi2 = i;
s += pozmax2[i];
}
printf("%lld", s);
return 0;
}