Pagini recente » Cod sursa (job #1019209) | Cod sursa (job #2607998) | Cod sursa (job #930110) | Cod sursa (job #311000) | Cod sursa (job #2553149)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 20000005;
int palin[NMAX], N;
char t[NMAX], s[NMAX];
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
fin >> (t + 1);
N = strlen(t + 1);
for (int i = 1;t[i];++i)
{
s[2 * i - 1] = '*';
s[2 * i] = t[i];
++N;
}
s[++N] = '*';
int left = 0, right = -1;
for (int i = 1;i <= N;++i)
{
int k;
if (i > right)
{
k = 1;
while (i - k >= 1 && i + k <= N && s[i - k] == s[i + k])
++k;
}
else
{
k = palin[left + right - i];
if (i + k - 1 < right)
palin[i] = k;
else
{
k = right - i + 1;
while (i - k >= 1 && i + k <= N && s[i - k] == s[i + k])
++k;
}
}
palin[i] = k;
if (i + k - 1 > right)
{
right = i + k - 1;
left = i - k + 1;
}
}
long long answer = 0;
for (int i = 1;i <= N;++i)
answer += (palin[i] / 2);
fout << answer << "\n";
fin.close();
fout.close();
return 0;
}