Pagini recente » Cod sursa (job #48822) | Cod sursa (job #174169) | Cod sursa (job #2902071) | Cod sursa (job #2215412) | Cod sursa (job #2802511)
#include <stdio.h>
#include <string.h>
#include <string>
FILE *fin, *fout;
const int NMAX = 1e6;
int N;
long long cnt;
char c_s[NMAX];
std :: string s;
int pal[2 * NMAX + 1];
int main() {
fin = fopen("pscpld.in", "r");
fscanf(fin, "%s", c_s);
fclose(fin);
N = strlen(c_s);
for(int i = 0; i < N; i++) {
s.push_back('$');
s.push_back(c_s[i]);
}
s.push_back('$');
N = s.size();
/*
for(int i = 0; i < N; i++) {
printf("%c ", s[i]);
}
printf("\n");
*/
for(int i = 0, l = 0, r = -1, k; i < N; i++) {
if(i > r) {
k = 1;
} else {
k = std :: min(pal[r + l - i], r - l + 1);
}
while(i - k >= 0 && i + k < N && s[i - k] == s[i + k]) {
k++;
}
pal[i] = k--;
if(r < i + k) {
r = i + k;
l = i - k;
}
cnt += (pal[i] >> 1LL);
}
/*
for(int i = 0; i < N; i++) {
printf("%d ", pal[i]);
}
printf("\n");
*/
fout = fopen("pscpld.out", "w");
fprintf(fout, "%lld\n", cnt);
fclose(fout);
return 0;
}