Pagini recente » Cod sursa (job #1313315) | Cod sursa (job #1403982) | Cod sursa (job #62807) | Cod sursa (job #1469142) | Cod sursa (job #2857999)
#include <fstream>
const int MAX_N = 1e6;
const int B = 257;
const int P = 1e9 + 7;
int prefH[1 + MAX_N], prefrevH[1 + MAX_N], power[1 + MAX_N];
int rangeHash(int l, int r) {
return (prefH[r] - (long long)prefH[l - 1] * power[r - l + 1] % P + B) % P;
}
int rangerevHash(int l, int r) {
return (prefrevH[l] - (long long)prefrevH[r + 1] * power[r - l + 1] % P + B) % P;
}
int cb_imp(int n, int pos) {
int st = 0, dr = (n - pos) / 2 , sol = -1;
while (st <= dr) {
int mijl = (st + dr) / 2;
if (rangeHash(pos - mijl, pos + mijl) == rangerevHash(pos - mijl, pos + mijl)) {
sol = mijl;
st = mijl + 1;
} else {
dr = mijl - 1;
}
}
return sol + 1;
}
int cb_par(int n, int pos) {
int st = 0, dr = (n - pos + 1) / 2, sol = 0;
while (st <= dr) {
int mijl = (st + dr) / 2;
if (rangeHash(pos - mijl + 1, pos + mijl) == rangerevHash(pos - mijl + 1, pos + mijl)) {
sol = mijl;
st = mijl + 1;
} else {
dr = mijl - 1;
}
}
return sol;
}
int cb(int n, int pos) {
return cb_imp(n, pos) + cb_par(n, pos);
}
int main() {
std::ifstream fin("pscpld.in");
std::ofstream fout("pscpld.out");
std::string s;
fin >> s;
int n = s.size();
for (int i = 1; i <= n; i++) {
prefH[i] = ((long long)prefH[i - 1] * B + (int)s[i - 1]) % P;
}
for (int i = n; i >= 1; i--) {
prefrevH[i] = ((long long)prefrevH[i + 1] * B + (int)s[i - 1]) % P;
}
power[0] = 1;
for (int i = 1; i <= MAX_N; i++) {
power[i] = (long long)power[i - 1] * B % P;
}
int answer = 0;
for (int i = 1; i <= n; i++) {
answer += cb(n, i);
}
fout << answer;
return 0;
}