Pagini recente » Cod sursa (job #1917321) | Cod sursa (job #258604) | Cod sursa (job #480961) | Cod sursa (job #2898171) | Cod sursa (job #2663644)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1000005;
int N, odd[NMAX], even[NMAX];
char s[NMAX];
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
fin >> (s + 1);
N = strlen(s + 1);
int l = 1, r = 0, k;
for (int i = 1;i <= N;++i)
{
if (i > r)
k = 1;
else
k = min(odd[l + r - i], r - i + 1);
while (i - k >= 1 && i + k <= N && s[i - k] == s[i + k])
++k;
odd[i] = k--;
if (i + k > r)
{
r = i + k;
l = i - k;
}
}
l = 1, r = 0;
for (int i = 1;i <= N;++i)
{
if (i > r)
k = 0;
else
k = min(even[l + r - i + 1], r - i + 1);
while (i - k - 1 >= 1 && i + k <= N && s[i - k - 1] == s[i + k])
++k;
even[i] = k--;
if (i + k > r)
{
r = i + k;
l = i - k - 1;
}
}
long long answer = 0;
for (int i = 1;i <= N;++i)
answer += odd[i] + even[i];
fout << answer << "\n";
fin.close();
fout.close();
return 0;
}