Pagini recente » Cod sursa (job #2098300) | Cod sursa (job #1865112) | Cod sursa (job #1510453) | Cod sursa (job #465586) | Cod sursa (job #1978229)
#include <cstdio>
#include <ctype.h>
const int MAX_N = 1000000;
const int BUFF = 4096;
char sir[2*MAX_N+1];
int plm[2*MAX_N+1];
char buff[BUFF];
int curs = BUFF - 1;
inline char getch(FILE *fin) {
curs++;
if(curs == BUFF) {
curs = 0;
fread(buff, 1, BUFF, fin);
}
return buff[curs];
}
int main() {
int n, n2, left, mid, right;
long long rez = 1LL;
char ch;
FILE *fin = fopen("pscpld.in", "r");
ch = getch(fin);
n = 0;
while(ch != EOF && ch != '\n' && ch != 0) {
if(isalpha(ch)) {
sir[2 * n] = ch;
++n;
}
ch = getch(fin);
}
fclose(fin);
n2 = 2 * n + 1;
plm[0] = 0;
left = mid = right = 0;
for(int i = 1; i < n2; ++i) {
if(i > right) { //iese rau in afara
plm[i] = 0;
mid = left = right = i;
while(left - 1 >= 0 && right + 1 < n2 && sir[left - 1] == sir[right + 1]) {
--left;
++right;
++plm[i];
}
} else {
plm[i] = plm[mid - (i - mid)];
if(i + plm[i] >= right) {
plm[i] = right - i;
mid = i;
left = i - (right - mid);
while(left - 1 >= 0 && right + 1 < n2 && sir[left - 1] == sir[right + 1]) {
--left;
++right;
++plm[i];
}
}
}
if(sir[i] == 0)
rez = rez + (plm[i] + 1) / 2;
else
rez = rez + plm[i] / 2 + 1;
}
FILE *fout = fopen("pscpld.out", "w");
fprintf(fout, "%lld", rez);
fclose(fout);
return 0;
}