Pagini recente » Cod sursa (job #1318798) | Cod sursa (job #680518) | Cod sursa (job #244912) | Cod sursa (job #1896879) | Cod sursa (job #3292851)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
string s, sir;
long long 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; ++i)
{
int capatdr = best + manacher[best];
int j = 2 * best - i;
if(i < capatdr)
{
manacher[i] = min(1LL * (capatdr - i), manacher[j]);
}
else
{
manacher[i] = 0;
}
while(i + manacher[i] < n && 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;
}