Pagini recente » Cod sursa (job #2930052) | Cod sursa (job #855211) | Winter Challenge 2008 | Cod sursa (job #412916) | Cod sursa (job #3291938)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
const int NMAX = 1000002;
int manacher[2 * NMAX];
int main()
{
string finalString = "@#";
string s;
f >> s;
for (int i = 0; i < s.size(); i++)
{
finalString += s[i];
finalString += "#";
}
finalString += "$";
int best = 0;
long long ans = 0;
for (int i = 1; i < finalString.size() - 1; i++)
{
if (best + manacher[best] > i)
{
manacher[i] = min(manacher[best] + best - i, manacher[2 * best - i]);
}
else
manacher[i] = 0;
while (finalString[i - manacher[i] - 1] == finalString[i + manacher[i] + 1])
{
manacher[i]++;
}
if (i + manacher[i] > best + manacher[best])
{
best = i;
}
ans += (manacher[i] + 1) / 2;
}
g<<ans;
return 0;
}