Pagini recente » Cod sursa (job #3124738) | Cod sursa (job #1078187) | Cod sursa (job #594199) | Cod sursa (job #929743) | Cod sursa (job #1513765)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 1000002
using namespace std;
int n, i, j, pos, a;
long long sol;
int len[maxN * 2];
char s[maxN * 2], S[maxN];
void read()
{
freopen("pscpld.in", "r", stdin);
gets(S + 1);
n = strlen(S + 1);
s[0] = '*';
for (i = 1; i <= n; ++ i)
{
s[(i - 1) * 2 + 1] = S[i];
s[i * 2] = '*';
}
n *= 2;
}
void solve()
{
pos = 0;
a = 0;
sol = 0;
for (i = 1; i <= n; ++ i)
{
if (i <= pos)
len[i] = min(len[2 * a - i], (pos - i));
while (i - len[i] - 1 >= 0 && i + len[i] + 1 <= n && s[i - len[i] - 1] == s[i + len[i] + 1])
++ len[i];
if (i + len[i] > pos)
{
pos = i + len[i];
a = i;
}
sol = (long long)(sol + (len[i] + 1) / 2) * 1LL;
}
}
void write()
{
freopen("pscpld.out", "w", stdout);
printf("%lld\n", sol);
}
int main()
{
read();
solve();
write();
return 0;
}