Pagini recente » Cod sursa (job #1023403) | Cod sursa (job #2632508) | Cod sursa (job #2837588) | Cod sursa (job #970522) | Cod sursa (job #2307192)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int drMax, posDrMax, manacher[2000005];
long long sol;
string s, a;
int main()
{
fin >> s;
a += '*';
for(int i = 0; i < s.size(); i++)
a += s[i], a += '*';
drMax = posDrMax = manacher[0] = 0;
for(int i = 1; i < a.size(); i++)
{
if(i > drMax)
{
int st = i - 1;
int dr = i + 1;
while(a[st] == a[dr] && st >= 0 && dr < a.size())
st--, dr++;
st++, dr--;
manacher[i] = dr - i;
drMax = dr;
posDrMax = i;
}
else if(i + manacher[i - 2 * (i - posDrMax)] < drMax)
manacher[i] = manacher[i - 2 * (i - posDrMax)];
else
{
int dr = drMax;
int st = 2 * i - drMax;
while(a[st] == a[dr] && st >= 0 && dr < a.size())
st--, dr++;
st++, dr--;
manacher[i] = dr - i;
drMax = dr;
posDrMax = i;
}
if(a[i] == '*')
sol += (manacher[i] + 1) / 2;
else
sol += (manacher[i] + 2) / 2;
}
fout << sol << '\n';
return 0;
}