Pagini recente » Cod sursa (job #2194590) | Cod sursa (job #1004480) | Cod sursa (job #1165733) | Cod sursa (job #1539661) | Cod sursa (job #1510503)
#include <cstdio>
#include <cstring>
typedef unsigned long long ull;
const int Nmax = 1000000;
const int BASE = 97;
char s[Nmax + 1];
char S[2 * Nmax + 2];
ull H[2 * Nmax + 2], h[2 * Nmax + 2];
ull pow[2 * Nmax + 2];
int n;
inline ull GetHash(int position, int siz) {
return H[position + siz - 1] - (position ? H[position - 1] * pow[siz] : 0ULL);
}
inline ull GetHashBackwards(int position, int siz) {
return h[position] - (position + siz < n ? h[position + siz] * pow[siz] : 0ULL);
}
int main(void) {
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
int i, lo, hi, mid;
long long r;
// citire
gets(s);
fclose(stdin);
r = strlen(s);
S[0] = '$';
for (i = 0; i < r; i++) {
S[2 * i + 1] = s[i];
S[2 * i + 2] = '$';
}
n = 2 * r + 2;
// precalculare puteri
pow[0] = 1ULL;
for (i = 1; i < n; i++) {
pow[i] = pow[i - 1] * BASE;
}
// precalculare hash
H[0] = S[0];
for (i = 1; i < n; i++) {
H[i] = H[i - 1] * BASE + S[i];
}
// precalculare hash pe invers
h[n - 1] = S[n - 1];
for (i = n - 2; i >= 0; i--) {
h[i] = h[i + 1] * BASE + S[i];
}
r = 0LL;
for (i = 1; i < n; i++) {
lo = 0;
hi = i + 1;
while (hi - lo > 1) {
mid = (lo + hi) / 2;
if (GetHash(i - mid, mid) == GetHashBackwards(i + 1, mid)) {
lo = mid;
} else {
hi = mid;
}
}
r += (lo + 1) / 2;
// printf("Reporting %d %d\n", i + 1, lo);
}
printf("%lld\n", r);
return 0;
}