Pagini recente » ONIS 2014, Clasament | Cod sursa (job #2704148) | Cod sursa (job #236061) | Cod sursa (job #1980994) | Cod sursa (job #2262529)
#include <fstream>
using namespace std;
ifstream fi ("pscpld.in");
ofstream fo ("pscpld.out");
string s;
char sir[2000005];
int lg,capatdr,mij,st,dr,simetric,sum,dist;
int dp[2000005];
int main()
{
fi>>s;
lg++;
sir[lg]='*';
lg++;
for (int i=0;i<s.size();i++)
{
sir[lg]=s[i];
lg++;
sir[lg]='*';
lg++;
}
capatdr=0;
mij=0;
for (int i=1;i<=lg;i++)
{
if (i>capatdr)
{
dp[i]=1;
st=i-1;dr=i+1;
while (st>=1 and dr<=lg and sir[st]==sir[dr])
{
st--;dr++;dp[i]++;
}
}
else
{
dist=i-mij;
simetric=mij-dist;
dp[i]=min(dp[simetric],capatdr-i);
st=i-dp[i];
dr=i+dp[i];
if (dr>capatdr)
{
while (st>=1 and dr<=lg and sir[st]==sir[dr])
{
st--;dr++;dp[i]++;
}
mij=i;capatdr=dr;
}
}
}
for (int i=1;i<=lg;i++) sum=sum+dp[i]/2;
fo<<sum;
return 0;
}