Pagini recente » Cod sursa (job #9708) | Clasament cex_3 | Cod sursa (job #2670870) | Cod sursa (job #1269667) | Cod sursa (job #2262541)
#include <fstream>
using namespace std;
ifstream fi ("pscpld.in");
ofstream fo ("pscpld.out");
string s;
char sir[2000005];
long long lg,capatdr,mij,st,dr,simetric,sum,dist;
long long 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++;
}
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]++;
}
mij=i;capatdr=i+dp[i]-1;
}
else
{
dist=i-mij;
simetric=mij-dist;
dp[i]=min(dp[simetric],capatdr-i+1);
st=i-dp[i];
dr=i+dp[i];
while (st>=1 and dr<=lg and sir[st]==sir[dr])
{
st--;dr++;dp[i]++;
}
if (dr-1>capatdr)
{
mij=i;capatdr=i+dp[i]-1;
}
}
}
for (int i=1;i<=lg;i++) sum=sum+dp[i]/2;
fo<<sum;
return 0;
}