Pagini recente » Rating Caliman Gheorghe (caliman_gh) | Cod sursa (job #524981) | Cod sursa (job #1772291) | Cod sursa (job #2226569) | Cod sursa (job #2041231)
#include <fstream>
#define VAL 2000005
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int N, i, j, mx;
int P[VAL], id;
long long ANS;
string s, S;
int main()
{
fin >> s;
N=2*s.size()+1;
S+='+';
S+='*';
for (i=0; i<s.size(); i++)
{
S+=s[i];
S+='*';
}
S+='-';
P[1]=1;
id=mx=1;
for (i=2; i<=N; i++)
{
if (i<=mx)
P[i]=min(P[2*id-i], mx-i);
else
P[i]=1;
while (S[i+P[i]]==S[i-P[i]])
P[i]++;
if (i+P[i]-1>mx)
{
id=i;
mx=i+P[i]-1;
}
if (i % 2==0)
ANS+=P[i] / 2;
else
ANS+=(P[i]-1) / 2;
}
fout << ANS << '\n';
fin.close();
fout.close();
return 0;
}