Pagini recente » Cod sursa (job #3134991) | Cod sursa (job #179527) | Cod sursa (job #2588597) | Cod sursa (job #2872815) | Cod sursa (job #2535499)
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
int P[2 * N], n;
char sir[N], s[2 * N];
int ans;
void Manacher()
{
int C = 0, R = 0;
for (int i = 1; i <= 2 * n + 1; i++)
{
int mirr = 2 * C - i;
if (i < R)
P[i] = min(P[mirr], R - i);
while (s[i + P[i] + 1] == s[i - P[i] - 1])
P[i]++;
if (i + P[i] >= R)
{
C = i;
R = i + P[i] - 1;
}
}
for (int i = 1; i <= 2 * n + 1; i++)
if (P[i] & 1)
ans += (P[i] / 2 + 1);
else
ans += (P[i] / 2);
fout << ans;
}
int main()
{
fin >> (sir + 1);
n = strlen(sir + 1);
s[0] = '$';
for (int i = 1; i <= 2 * n + 1; i++)
{
if (i & 1)
s[i] = '#';
else
s[i] = sir[i / 2];
}
s[2 * n + 2] = '@';
Manacher();
return 0;
}