Pagini recente » Cod sursa (job #3154498) | Cod sursa (job #273824) | Cod sursa (job #2155666) | Cod sursa (job #683150) | Cod sursa (job #2416635)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int NMAX = 1000000;
long long ans;
int manacher[2 * NMAX + 5];
string s;
void Manacher()
{
int drMax = 0;
int posDrMax = 0;
for(int i = 1; i < s.size(); i++)
{
if(i > drMax)
{
int st = i - 1;
int dr = i + 1;
while(s[st] == s[dr] && st >= 0 && dr < s.size())
st--, dr++;
st++, dr--;
manacher[i] = dr - i;
drMax = dr;
posDrMax = i;
}
else
{
if(i + manacher[2 * posDrMax - i] < drMax)
manacher[i] = manacher[2 * posDrMax - i];
else
{
int st = 2 * i - drMax;
int dr = drMax;
while(s[st] == s[dr] && st >= 0 && dr < s.size())
st--, dr++;
st++, dr--;
manacher[i] = dr - i;
drMax = dr;
posDrMax = i;
}
}
if(s[i] == '$')
ans += 1LL * (manacher[i] + 1) / 2;
else
ans += 1LL * (manacher[i] + 2) / 2;
}
}
int main()
{
string aux;
fin >> aux;
s += '$';
for(auto it : aux)
s += it, s += '$';
Manacher();
fout << ans << '\n';
return 0;
}