Pagini recente » Cod sursa (job #3310881) | Cod sursa (job #1167857) | Cod sursa (job #3268163) | Cod sursa (job #2254000) | Cod sursa (job #1514237)
#include <bits/stdc++.h>
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013
using namespace std;
typedef long long LL;
LL n, rgt, i, pal, ok, sol;
LL l[1000005];
char sir[1000005];
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
gets(sir + 1);
n = strlen(sir + 1);
rgt = pal = 0;
for(i = 1; i <= n; i++)
{
if(rgt >= i)
l[i] = min(l[pal * 2 - i], rgt - i + 1);
l[i] = max(l[i], 1LL);
while(sir[ i + l[i] ] == sir[ i - l[i] ] && i + l[i] <= n && i - l[i] >= 1)
l[i]++;
sol += l[i];
if(i + l[i] - 1 > rgt)
{
rgt = i + l[i] - 1;
pal = i;
}
}
rgt = pal = 0;
l[1] = 0;
for(i = 2; i <= n; i++)
{
l[i] = 0;
if(rgt >= i)
l[i] = min(l[pal * 2 - i], rgt - i + 1);
l[i] = max(l[i], 0LL);
while(sir[ i + l[i] ] == sir[ i - l[i] - 1 ] && i + l[i] <= n && i - l[i] - 1 >= 1)
l[i]++;
sol += l[i];
if(i + l[i] - 1 > rgt)
{
rgt = i + l[i] - 1;
pal = i;
}
}
printf("%lld", sol);
return 0;
}