Pagini recente » Cod sursa (job #1622667) | Cod sursa (job #3129155) | Cod sursa (job #633483) | Cod sursa (job #2822071) | Cod sursa (job #1968857)
#include <fstream>
#include <cstring>
#define nmax 1000005
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
char a[nmax],s[nmax<<1];
int n,m,c,ans,dp[nmax<<1];
void manacher()
{
int i,c=0;
for (i=2;i<=n;i++) {
dp[i]=1;
if(c+dp[c]>i)
dp[i]=min(c+dp[c]-i,dp[2*c-i]);
dp[i]=max(1,dp[i]);
while (i-dp[i]>0&&i+dp[i]<=n&&s[i-dp[i]]==s[i+dp[i]])
++dp[i];
if (i%2==0)
ans+=(dp[i])/2;
else
ans+=(dp[i]-1)/2;
if(i+dp[i]>c+dp[c])
c=i;
}
}
int main()
{
int i,j;
f>>a+1;
n=strlen(a+1);
for (i=1,m=0;i<=n;i++) {
s[++m]='!';
s[++m]=a[i];
}
s[++m]='!';
n=m;
manacher();
g<<ans;
return 0;
}