Pagini recente » Cod sursa (job #1218526) | Cod sursa (job #2543128) | Cod sursa (job #2249216) | Cod sursa (job #310399) | Cod sursa (job #1391349)
#include <cstdio>
#include <cstring>
#define Nmax 1000100
#define Smax 2000100
using namespace std;
char c[Nmax],A[Smax];
int N,DP[Smax];
int mini(int a,int b){
if(a < b) return a;
return b;
}
void Read()
{
scanf("%s",c);
int lg = strlen(c);
A[0] = '$';A[1] = '#'; N = 1;
for(int i = 0; i < lg; ++i){
A[++N] = c[i];
A[++N] = '#';
}
A[N+1] = 0;
}
void Manacher()
{
int right,center,_i;
right = center = 0;
long long rez = 0;
for(int i = 1; i <= N; ++i)
{
_i = (center<<1) - i; /// simetricul fata de centru
if(i <= right)
DP[i] = mini(DP[_i], right - i);
while(A[i - DP[i] - 1] == A[i + DP[i] + 1])
++DP[i];
if(i + DP[i] > right){
right = i + DP[i];
center = i;
}
rez += (DP[i] + 1) >> 1;
}
printf("%lld\n",rez);
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
Read();
Manacher();
return 0;
}