Pagini recente » Cod sursa (job #1280160) | Cod sursa (job #2467931) | Cod sursa (job #675051) | Cod sursa (job #2037349) | Cod sursa (job #3195464)
#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(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;
}