Pagini recente » Cod sursa (job #3288568) | Cod sursa (job #3275764) | Cod sursa (job #3241505) | Cod sursa (job #3250232) | Cod sursa (job #3292849)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
string s, sir;
int manacher[2000001], best = 0, n, nrpal = 0;
int main()
{
cin>>s;
n = s.size();
sir = "%$";
for(int i = 0; i < n; ++i)
{
sir += s[i];
sir += "$";
}
sir += "#";
n = sir.size();
for(int i = 1; i < n - 1; ++i)
{
int capatdr = best + manacher[best];
int j = 2 * best - i;
if(i < capatdr)
{
manacher[i] = min(capatdr - i, manacher[j]);
}
else
{
manacher[i] = 0;
}
while(i + manacher[i] < n - 1 && sir[i + manacher[i] + 1] == sir[i - manacher[i] - 1])
{
++manacher[i];
}
if(i + manacher[i] > capatdr)
best = i;
nrpal += (manacher[i] + 1) / 2;
}
cout<<nrpal<<"\n";
return 0;
}