Pagini recente » Cod sursa (job #120475) | Cod sursa (job #440345) | Cod sursa (job #1721725) | Cod sursa (job #1600768) | Cod sursa (job #2354299)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int l, r, len, d[2000005], N;
long long k;
char s[2000005];
int main()
{
fin.getline(s, 1000001);
N = strlen(s);
for (int i = N - 1; i >= 0; i--)
s[i * 2] = s[i];
N = 2 * N - 1;
for (int i = 1; i < N; i += 2)
s[i] = '#';
for (int i = 0; i < N; i++)
{
if (i > r)
{
len = 1;
while (s[i - len] == s[i + len])
{
len++;
if (i - len < 0 || i + len == N)
break;
}
len--;
d[i] = len;
r = i + len;
l = i - len;
}
else
{
len = min(d[l + r - i], r - i);
while (s[i - len] == s[i + len])
{
len++;
if (i - len < 0 || i + len == N)
break;
}
len--;
d[i] = len;
if (i + len > r)
{
r = i + len;
l = i - len;
}
}
}
for (int i = 0; i < N; i++)
k += d[i] / 2 + 1 - i % 2;
fout << k;
return 0;
}