Pagini recente » Cod sursa (job #2885539) | Cod sursa (job #2240130) | Cod sursa (job #1958628) | Cod sursa (job #1466655) | Cod sursa (job #473494)
Cod sursa(job #473494)
#include <fstream>
#include <stdio.h>
using namespace std;
long long suma;
char s[2000000];
typedef struct{
int c,s;} palindrom;
int pl,n,i,d1,d2,d3,lg[2000000];
int minim(int a,int b,int c)
{
if((a<b)&&(a<c)) return a;
if((b<a)&&(b<c)) return b; else return c;
}
palindrom pal[2000000];
int main()
{
freopen("pscpld.in","r",stdin);
ofstream fo("pscpld.out");
while(1) { s[++n]=getchar(); if(s[n]=='\n') break; s[++n]=' '; }
n-=2;
for(i=1;i<=n;i++)
{
if(s[i]!=' ') lg[i]=1;
if(pal[i].s)
{
if((pal[i].s%2==1)&&(pal[i].c%2==1))
{
d1=(pal[i].c/2+1)-(pal[i].s/2+1)+1;
d2=(pal[i].s/2+1)-(pal[i].c/2+1)+lg[pal[i].c];
d3=lg[pal[i].s];
lg[i]=minim(d1,d2,d3);
}
if((pal[i].s%2==1)&&(pal[i].c%2==0))
{
d1=(pal[i].c/2)-(pal[i].s/2+1)+1;
d2=(pal[i].s/2+1)-(pal[i].c/2)+lg[pal[i].c];
d3=lg[pal[i].s];
lg[i]=minim(d1,d2,d3);
}
if((pal[i].s%2==0)&&(pal[i].c%2==1))
{
d1=(pal[i].c/2+1)-(pal[i].s/2+1)+1;
d2=(pal[i].s/2)-(pal[i].c/2+1)+lg[pal[i].c];
d3=lg[pal[i].s];
lg[i]=minim(d1,d2,d3);
}
if((pal[i].s%2==0)&&(pal[i].c%2==0))
{
d1=(pal[i].c/2)-(pal[i].s/2+1)+1;
d2=(pal[i].s/2)-(pal[i].c/2)+lg[pal[i].c];
d3=lg[pal[i].s];
lg[i]=minim(d1,d2,d3);
}
}
if(s[i]!=' '){
pl=lg[i]*2;
while((i+pl<=n)&&(i-pl>=1))
{
if(s[i+pl]!=s[i-pl]) break;
pal[i+pl-1].s=i-pl+1;
pal[i+pl].s=i-pl;
pal[i+pl-1].c=i;
pal[i+pl].c=i;
lg[i]++;
pl+=2;
}
}
if(s[i]==' '){
pl=lg[i]*2+1;
while((i+pl<=n)&&(i-pl>=1))
{
if(s[i+pl]!=s[i-pl]) break;
pal[i+pl-1].s=i-pl+1;
pal[i+pl].s=i-pl;
pal[i+pl-1].c=i;
pal[i+pl].c=i;
lg[i]++;
pl+=2;
}
}
suma+=lg[i];
}
fo<<suma<<"\n";
fo.close();
return 0;
}