Pagini recente » Cod sursa (job #283366) | Cod sursa (job #2326829) | Cod sursa (job #1626483) | Cod sursa (job #2144960) | Cod sursa (job #2175136)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 1e6 + 5;
char str[MAXN + 1];
char aux[2 * MAXN + 1];
int len[2 * MAXN + 1];
int main() {
FILE *fi, *fout;
int i, n;
fi = fopen("pscpld.in" ,"r");
fout = fopen("pscpld.out" ,"w");
fgets(str + 1, MAXN, fi);
int sz = strlen(str + 1) - 1;
n = 0;
aux[++n] = '*';
for(i = 1; i <= sz; i++) {
aux[++n] = str[i];
aux[++n] = '*';
}
int pos = 0;
for(i = 1; i <= n; i++) {
if(pos + len[pos] >= i) {
len[i] = min(pos + len[pos] - i, len[2 * pos - i]);
}
while(i - len[i] > 0 && i + len[i] <= n && aux[i - len[i]] == aux[i + len[i]])
len[i]++;
if(i + len[i] > pos + len[pos])
pos = i;
}
long long ans = 0;
for(i = 1; i <= n; i++) {
ans += len[i] / 2;
}
fprintf(fout,"%lld" ,ans);
fclose(fi);
fclose(fout);
return 0;
}