Pagini recente » Cod sursa (job #309442) | Cod sursa (job #337810) | Cod sursa (job #1910774) | Cod sursa (job #1783013) | Cod sursa (job #3195462)
#include <fstream>
using namespace std;
using ll = long long;
const int NMAX = 2000012;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int v[NMAX];
int main()
{
string a, s;
cin >> a;
s += '&';
s += '*';
for(int i = 0; i < a.size(); i++) {
s += a[i];
s += '*';
}
s += '#';
int imp = 0, end = 0;
for(int i = 0; i < s.size(); i++) {
if(i < end && v[2 * imp - i] < end - i)
v[i] = v[2 * imp - i];
else {
v[i] = max(0, end - i);
while(i + v[i] + 1 < s.size() && i - v[i] - 1 >= 0 && s[i + v[i] + 1] == s[i - v[i] - 1])
v[i]++;
imp = i;
end = i + v[i];
}
}
ll ans = 0;
for(int i = 0; i < s.size(); i++)
ans += (v[i] + 1) / 2;
cout << ans;
/*for(int i = 0; i < s.size(); i++)
cout << s[i] << " ";
cout << '\n';
for(int i = 0; i < s.size(); i++)
cout << v[i] << " ";*/
return 0;
}