Pagini recente » Cod sursa (job #1870510) | Cod sursa (job #2368838) | Cod sursa (job #1549598) | Cod sursa (job #1789360) | Cod sursa (job #2836105)
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
string a;
int s[2000005];
int main()
{
char ch;
while (in >> ch)
{
a.push_back('*');
a.push_back(ch);
}
int l = 0,r = 0;
for (int i = 1; i < a.size(); i++)
{
if (i > r)
{
int p1 = i - 1,p2 = i + 1;
while (p1 >= 0 and p2 <= a.size() and a[p1] == a[p2])
{
s[i]++;
p1--;
p2++;
}
l = i - s[i];
r = i + s[i];
}
else
{
int c = (r + l) / 2;
int d = i - c;
int pi = c - d;
if (s[pi] < pi - l)
s[i] = s[pi];
else
{
s[i] = r - i;
int p1 = 2 * i - r - 1,p2 = r + 1;
while (p1 >= 0 and p2 <= a.size() and a[p1] == a[p2])
{
s[i]++;
p1--;
p2++;
}
r = i + s[i];
l = i - s[i];
}
}
}
long long sum = 0;
for (int i = 1; i <= a.size(); i++)
sum += s[i] / 2;
sum += a.size() / 2;
out << sum;
return 0;
}