Pagini recente » Cod sursa (job #1510758) | Cod sursa (job #1784724) | Cod sursa (job #2457644) | Cod sursa (job #877935) | Cod sursa (job #62020)
Cod sursa(job #62020)
#include <cstdio>
#include <string>
using namespace std;
#define Nmax 1000100
char v[Nmax];
int a[Nmax][2], sol, N;
// pt 0 consider cazul cu mij impar \
pt 1 consider cazul cu mij par a[1][i] = lung la pal care incepe cu v[i],v[i+1]
void ext1(int mij)
{
int st,dr;
if(a[0][mij] == 0)
a[0][mij] = 1;
st = mij - a[0][mij] + 1;
dr = mij + a[0][mij] - 1;
// printf("expandez din %d\n",mij);
// printf("limitele temp sunt %d %d\n",st,dr);
while(st>0 && dr+1<N && v[st-1] == v[dr+1])
{
// printf("am expandat\n");
++a[0][mij];
--st; ++dr;
a[0][dr] = a[0][st];
if(st < dr && v[st] == v[st+1])
a[1][dr-1] = a[1][st];
}
sol += a[0][mij];
}
void ext2(int mij)
{
int st,dr;
if(a[1][mij] == 0)
a[1][mij] = v[mij] == v[mij+1];
if(a[1][mij] == 0)
return ;
st = mij - a[1][mij] + 1;
dr = mij + a[1][mij] ;
// printf("expandez din %d\n",mij);
// printf("limitele temp sunt %d %d\n",st,dr);
while(st>0 && dr+1<N && v[st-1] == v[dr+1])
{
// printf("am expandat\n");
++a[1][mij];
--st; ++dr;
a[0][dr] = a[0][st];
if(st < dr && v[st] == v[st+1])
a[1][dr-1] = a[1][st];
}
sol += a[1][mij];
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
fgets(v,Nmax,stdin);
N = strlen(v) - 1;
for(int i=0;i<N;++i)
ext1(i), ext2(i);
printf("%d\n",sol);
/*
fputs(v,stdout);
for(int i=0;i<N;++i)
printf("par %d | impar %d\n",a[1][i],a[0][i]);
*/
return 0;
}