Pagini recente » Cod sursa (job #1104511) | Cod sursa (job #831075) | Cod sursa (job #2901513) | Cod sursa (job #47177) | Cod sursa (job #75283)
Cod sursa(job #75283)
#include <cstdio>
#include <cstring>
#define maxn (1 << 21)
char s[maxn];
int n, f[maxn], fi;
typedef long long LL;
inline int min(const int a, const int b) {
return (a < b) ? a : b;
}
int main() {
int i, rec, p, p1, p2;
LL ans;
FILE *fin,*fout;
fin=fopen("pscpld.in","r");
fout=fopen("pscpld.out","w");
fscanf(fin,"%s",s);
fclose(fin);
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){
if (i <= p)
{fi = f[(rec << 1) - i];
if (fi > p - i) fi=p-i;
}
else fi=0;
while (i - fi - 1>= 0&&i + fi + 1<= n&&s[i-fi-1] == s[i+fi+1]) ++fi;
if (i + fi > p){ //>rec
p = i+fi;
rec = i;
}
ans += (fi + 1) >> 1;
f[i] = fi;
}
fprintf(fout,"%lld\n", ans);
fclose(fout);
return 0;
}