Pagini recente » Cod sursa (job #1838178) | Cod sursa (job #954924) | Cod sursa (job #2473866) | Cod sursa (job #2336715) | Cod sursa (job #3156168)
#include <fstream>
#include <string>
using namespace std;
const long long max_size = 1e6 + 3;
ifstream in ("pscpld.in");
ofstream out ("pscpld.out");
int p[2 * max_size];
signed main ()
{
string x, s;
in >> x;
s += '$';
for (long long i = 0; i < x.size(); i++)
{
s += x[i];
s += '$';
}
long long ans = 0;
int dr = 0, n = s.size() - 1, poz = 0;
for (int i = 1; i <= n; i++)
{
long long x = 2 * poz - 1;
if (dr > i)
{
p[i] = min(p[x], dr - i);
}
while (i >= p[i] + 1 && i + p[i] - 1 <= n && s[i - p[i] - 1] == s[i + p[i] + 1])
{
p[i]++;
}
if (i + p[i] > dr)
{
dr = i + p[i];
poz = i;
}
if (i % 2 == 1)
{
ans += 1LL * (p[i] + 1) / 2;
}
else
{
ans += 1LL * p[i] / 2;
}
}
out << ans;
in.close();
out.close();
return 0;
}