Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3332205) | Monitorul de evaluare | Cod sursa (job #1514233)
#include <bits/stdc++.h>
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013
using namespace std;
int n, rgt, i, pal, ok, sol;
int 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], 1);
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], 0);
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("%d", sol);
return 0;
}