Pagini recente » Cod sursa (job #3041333) | Cod sursa (job #3193868) | Cod sursa (job #2557147) | Cod sursa (job #2958232) | Cod sursa (job #1053948)
#include<stdio.h>
#include<vector>
#include<unordered_map>
#include<set>
#include<algorithm>
#include<cstring>
#define maxlen 1000005
#define maxn 605
#define maxcif 7005
using namespace std;
char sir[maxlen];
int D[maxlen];
inline void pscpld ( char *sir , int len , int *D , int add = 0 ) {
int st = 1,dr = 0;
for ( int i = 1 ; i <= len ; ++i ){
if ( add && sir[i] != sir[i+1] ){
D[i] = 0; continue ;
}
if ( i >= dr ){
st = i,dr = i+add; D[i] = 1;
while ( st > 1 && dr < len && sir[st-1] == sir[dr+1] ){
--st; ++dr;
++D[i];
}
}
else{
int centre = (st+dr+add)>>1;
D[i] = min(D[centre+centre-i-add],dr-i+1-add);
int p = i-D[i]+1,u = i+D[i]-1+add;
while ( p > 1 && u < len && sir[p-1] == sir[u+1] ){
--p; ++u;
++D[i];
}
if ( u > dr ) st = p,dr = u;
}
}
}
inline long long getNumberOfPalindroms ( char *sir ){
int len = strlen(sir+1);
long long pals = 0;
pscpld(sir,len,D);
for ( int i = 1 ; i <= len ; ++i ) pals += D[i];
pscpld(sir,len,D,1);
for ( int i = 1 ; i <= len ; ++i ) pals += D[i];
return pals;
}
int main () {
//#ifndef ONLINE_JUDGE
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
//#endif
scanf("%s",sir+1);
long long palindroms = getNumberOfPalindroms(sir);
// //n = 15; palindroms = 2;
// fscanf(stdin,"%d %d",&n,&palindroms);
printf("%lld\n",palindroms);
return 0;
}