Pagini recente » Cod sursa (job #1624683) | Cod sursa (job #2840770) | Cod sursa (job #10837) | Cod sursa (job #2416684) | Cod sursa (job #75280)
Cod sursa(job #75280)
#include <cstdio>
#include <cstring>
#define maxn (1 << 21)
static char s[maxn];
static int n, f[maxn], fi;
typedef long long LL;
static inline int min(const int a, const int b) {
return (a < b) ? a : b;
}
int main() {
static int i, rec, p, tmp, p1, p2;
static LL ans;
FILE *fin,*fout;
fin=fopen("pscpld.in","r");
fout=fopen("pscpld.out","w");
fscanf(fin,"%s",s);
n = strlen(s);
p1 = (n << 1);
p2 = n - 1;
while (p1 >= 0) {
if (p1 & 1)
s[p1--] = s[p2--];
else
s[p1--] = '.';
}
n <<= 1;
ans = 0;
for (rec = 0, p = -1, i = 0; i <= n; ++i){
for (fi = (i <= p) ? min(f[(rec << 1) - i], p - i) : 0; ((p1 = i - fi - 1) >= 0) && ((p2 = i + fi + 1) <= n) && (s[p1] == s[p2]); ++fi);
if ((tmp = i + fi) > rec){
p = tmp;
rec = i;
}
ans += (fi + 1) >> 1;
f[i] = fi;
}
fprintf(fout,"%lld\n", ans);
return 0;
}