Pagini recente » Cod sursa (job #1910434) | Cod sursa (job #1591889) | Cod sursa (job #3205972) | Cod sursa (job #1961393) | Cod sursa (job #1303280)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 2000005
using namespace std;
char c[Nmax],a[Nmax];
int DP[Nmax];
int nr,N;
long long ans;
void read()
{
fgets(c+1,Nmax-1,stdin);
c[0]='#';
if(c[strlen(c)-1] == '\n')
c[strlen(c)-1] = 0;
nr = strlen(c+1);
}
void expand()
{
a[N++] = '&';
a[N] = '#';
for(int i = 1 ; i <= nr; ++i)
{
a[++N] = c[i];
a[++N] = '#';
}
a[++N] = '$';
}
void manacher()
{
int center,right,_i;
center = right = 0;
for(int i = 1; i < N; ++i)
{
_i = 2*center - i;
if(right > i)
DP[i] = min(DP[_i],right - i);
while(a[i - DP[i] - 1] == a[i + DP[i] + 1])
++DP[i];
if( i + DP[i] > right){
center = i;
right = i + DP[i];
}
ans += (DP[i] + 1) / 2;
}
printf("%lld\n",ans);
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
read();
expand();
manacher();
return 0;
}