Pagini recente » Cod sursa (job #2728181) | Cod sursa (job #49045) | Cod sursa (job #2006800) | Cod sursa (job #1289005) | Cod sursa (job #2029892)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char str[200010], aux[200010];
int lsp[200010];
int main ()
{
freopen ("pscpld.in", "r", stdin);
freopen ("pscpld.out", "w", stdout);
fgets (aux + 1, 100010, 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;
}