Pagini recente » Cod sursa (job #1583948) | Cod sursa (job #1651134) | Cod sursa (job #1639485) | Diferente pentru info-oltenia-2018/individual/clasament/9 intre reviziile 4 si 3 | Cod sursa (job #1151233)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 2000010;
int M, N, P[NMAX], R, C;
long long Ans;
char S[NMAX], A[NMAX];
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
gets(A + 1); M = strlen(A + 1);
S[++ N] = '*';
for(int i = 1; i <= M; ++ i)
S[++ N] = A[i], S[++ N] = '*';
for(int i = 1; i <= N; ++ i)
{
if(i <= R) P[i] = max(min(P[2 * C - i], R - i), 1);
while(i - P[i] >= 1 && i + P[i] <= N && S[i - P[i]] == S[i + P[i]]) P[i] ++;
P[i] --;
if(i + P[i] > R) C = i, R = i + P[i];
Ans += (P[i] + 1) / 2;
}
printf("%lld\n", Ans);
}