Pagini recente » Cod sursa (job #1884528) | Cod sursa (job #1098831) | Cod sursa (job #3180966) | Cod sursa (job #64440) | Cod sursa (job #2802520)
#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(i + k > r) {
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;
}