Pagini recente » Cod sursa (job #975344) | Cod sursa (job #1692526) | Cod sursa (job #1960349) | penultimainaintedeotv | Cod sursa (job #62193)
Cod sursa(job #62193)
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
#define Nmax 1000100
char v[Nmax];
int a1[Nmax], a0[Nmax], sol, N;
void ext1(int mij);
void ext2(int mij);
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
fgets(v,Nmax,stdin);
N = strlen(v) ;
for(int i=0;i<N;++i)
{
ext1(i), ext2(i);
}
for(int i=0;i<N;++i)
sol += a0[i] + a1[i];
printf("%d\n",sol);
/*
fputs(v,stdout);
for(int j=0;j<N;++j)
printf("par %d | impar %d\n",a1[j],a0[j]);
printf("\n");
*/
return 0;
}
void ext1(int mij)
{
int st,dr;
if(a0[mij] == 0)
a0[mij] = 1;
st = mij - a0[mij] + 1;
dr = mij + a0[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");
++a0[mij];
--st; ++dr;
a0[dr] = max(a0[st],a0[dr]);
if(st < dr && v[st] == v[st+1])
a1[dr-1] = a1[st];
}
}
void ext2(int mij)
{
int st,dr;
if(a1[mij] == 0)
a1[mij] = v[mij] == v[mij+1];
if(a1[mij] == 0)
return ;
st = mij - a1[mij] + 1;
dr = mij + a1[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");
++a1[mij];
--st; ++dr;
a0[dr] = max(a0[st],a0[dr]);
if(st < dr && v[st] == v[st+1])
a1[dr-1] = a1[st];
}
}