Pagini recente » Borderou de evaluare (job #2616879) | Borderou de evaluare (job #711726) | Borderou de evaluare (job #1689176) | Borderou de evaluare (job #1978043) | Cod sursa (job #2412191)
#include <bits/stdc++.h>
#define MAXN 1000000
int n;
char S[1 + MAXN];
int LPS[2 * MAXN];
void Manacher(char S[], int n, int LPS[]){
char T[2 * MAXN];
for(int i = 1; i < n; i++){
T[2 * i - 1] = S[i];
T[2 * i] = '*';
}
T[2 * n - 1] = S[n];
n = 2 * n - 1;
int p = 1;
for(int i = 1; i <= n; i++){
LPS[i] = std::max(0, std::min(p + LPS[p] - i, LPS[2 * p - i]));
while(i - (LPS[i] + 1) >= 1 && i + (LPS[i] + 1) <= n &&
T[i - (LPS[i] + 1)] == T[i + (LPS[i] + 1)]) LPS[i]++;
if(i + LPS[i] > p + LPS[p])
p = i;
}
}
int main(){
FILE*fi,*fo;
fi = fopen("pscpld.in","r");
fo = fopen("pscpld.out","w");
char c = fgetc(fi);
while('a' <= c && c <= 'z'){
S[++n] = c;
c = fgetc(fi);
}
Manacher(S, n, LPS);
long long ans = 0;
for(int i = 1; i < 2 * n; i++)
if(i % 2 == 1) ans += (LPS[i]) / 2 + 1;
else ans += (LPS[i] + 1) / 2;
fprintf(fo,"%lld", ans);
return 0;
}