Pagini recente » Cod sursa (job #1292142) | Cod sursa (job #1279579) | Cod sursa (job #1716246) | Cod sursa (job #1302642) | Cod sursa (job #1335937)
#include <stdio.h>
#define MAXN 1000000
char v[2 * MAXN + 1];
int rez[2 * MAXN + 1];
void solve(int n){
int i, dr = 0, st = 0, ci, j;
for(i = 0; i <= n; i++){
if(i <= dr){
ci = st + dr - i;
if(ci - rez[ci] / 2 >= st)
j = i + rez[ci] / 2 + 1;
else
j = dr + 1;
}
else
j = i + 1;
while(i - (j - i) >= 0 && j <= n && v[j] == v[i - (j - i)])
j++;
j--;
rez[i] = 2 * (j - i) + 1;
if(dr < j){
dr = j;
st = i - (j - i);
}
}
}
int main(){
FILE *in = fopen("pscpld.in", "r");
int n = 1, i;
char ch = fgetc(in);
while(ch >= 'a' && ch <= 'z'){
v[n] = ch;
n += 2;
ch = fgetc(in);
}
fclose(in);
n--;
solve(n);
int sum = 0;
for(i = 0; i <= n; i++){
sum += rez[i] / 4;
}
sum += (n + 1) / 2;
FILE *out = fopen("pscpld.out", "w");
fprintf(out, "%d", sum);
fclose(in);
return 0;
}