Pagini recente » Cod sursa (job #2465132) | Cod sursa (job #2915829) | Cod sursa (job #475839) | Cod sursa (job #40098) | Cod sursa (job #1678310)
#include <fstream>
#include <string.h>
#define nMax 2000008
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int n;
int dp[nMax];
char S[nMax], sir[nMax];
void read()
{
fin>>S+1;
for(int i=1;S[i]!=0;i++)
{
sir[++n]='#';
sir[++n]=S[i];
}
sir[++n]='#';
}
void solve()
{
int C=0, R=0;
for(int i=1;i<=n;i++)
{
if(i<=R)
dp[i]=min(dp[C-(i-C)], R-i+1);
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;
}
}
}
void write()
{
long long Sol=0;
for(int i=1;i<=n;i++)
Sol+=dp[i]/2;
fout<<Sol;
}
int main()
{
read();
solve();
write();
return 0;
}