Pagini recente » Cod sursa (job #152027) | Cod sursa (job #548639) | Cod sursa (job #1690936) | Cod sursa (job #2759972) | Cod sursa (job #2029939)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char str[2000010], aux[2000010];
int lsp[2000010];
int main ()
{
freopen ("pscpld.in", "r", stdin);
freopen ("pscpld.out", "w", stdout);
fgets (aux + 1, 1000010, stdin);
int k = strlen (aux + 1);
int n = 0;
str[++n] = '#';
for (int i = 1; i < k; ++i)
str[++n] = aux[i],
str[++n] = '#';
lsp[2] = 1;
int dr = 3, poz = 2;
for (int i = 3; i <= n; ++i)
if (dr - i > lsp[2 * poz - i]) lsp[i] = lsp[2 * poz - i];
else
{
for (++dr; dr <= n && 2 * i - dr > 0 && str[dr] == str[2 * i - dr]; ++dr);
--dr;
lsp[poz = i] = dr - i;
}
long long rez = 0LL;
for (int i = 1; i <= n; ++i)
rez += 1LL * (lsp[i] + 1) / 2LL;
printf ("%lld\n", rez);
return 0;
}