Pagini recente » Cod sursa (job #1729859) | Cod sursa (job #1624272) | Cod sursa (job #2698392) | Cod sursa (job #2094701) | Cod sursa (job #1923155)
#include <fstream>
#include <string.h>
#define nMax 1000005
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char S[nMax], sir[2*nMax];
int n, dp[2*nMax];
int main()
{
fin>>S+1;
for(int i=1; S[i]!=0; i++)
{
sir[++n]='#';
sir[++n]=S[i];
}
sir[++n]='#';
long long Sol=0;
int C=0, R=0;
for(int i=1; i<=n; i++)
{
if(i<=R)
dp[i]=min(R-i+1, dp[C-(i-C)]);
while(sir[i+dp[i]]==sir[i-dp[i]] && i+dp[i]<=n && i-dp[i]>=1)
dp[i]++;
if(i+dp[i]-1>R)
{
R=i+dp[i]-1;
C=i;
}
Sol+=dp[i]/2;
}
fout<<Sol;
}