Pagini recente » Cod sursa (job #1806531) | Cod sursa (job #634016) | Cod sursa (job #1282701) | Cod sursa (job #1651510) | Cod sursa (job #3236689)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000000;
const int MOD = 1e9 + 7;
string s;
long long H[MAX + 3];
long long H1[MAX + 3];
long long pww[MAX + 3];
int N;
long long pw(long long A, long long N) {
if(N == 0) {
return 1;
}
if(N % 2 == 1) {
return (1LL * A * pw(A, N - 1)) % MOD;
}
long long P = pw(A, N / 2) % MOD;
return (1LL * P * P) % MOD;
}
bool hash2(int len, int i) {
long long hash1 = 0, hash2 = 0;
//if(i - 1 - len >= 0)
hash1 = ((1LL * (H[i - 1] - H[i - 1 - len] + MOD) % MOD) * 1LL * pw(pww[i - len], MOD - 2)) % MOD;
//else hash1 = ((1LL * (H[i - 1]) % MOD)) % MOD;
hash2 = ((1LL * (H1[i] - H1[i + len] + MOD) % MOD) * 1LL * pw(pww[N - i - len], MOD - 2)) % MOD;
//if(len == 1)
//cout << hash1 << ' ' << hash2 << '\n';
if(hash1 == hash2) return true;
return false;
}
bool hash1(int len, int i) {
long long hash1 = 0, hash2 = 0;
//if(i - 1 - len >= 0)
hash1 = ((1LL * (H[i - 1] - H[i - 1 - len] + MOD) % MOD) * 1LL * pw(pww[i - len], MOD - 2)) % MOD;
//else hash1 = ((1LL * (H[i - 1]) % MOD)) % MOD;
hash2 = ((1LL * (H1[i + 1] - H1[i + len + 1] + MOD) % MOD) * 1LL * pw(pww[N - i - len - 1], MOD - 2)) % MOD;
//if(len == 1)
//cout << hash1 << ' ' << hash2 << '\n';
if(hash1 == hash2) return true;
return false;
}
int main() {
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> s;
N = s.size();
pww[0] = 1;
for(int i = 1; i <= N; i++) {
pww[i] = (1LL * pww[i - 1] * 26) % MOD;
}
H[0] = (s[0] - 'a' + 1);
for(int i = 0; i < N; i++) {
H[i] = (H[i - 1] + 1LL * (s[i] - 'a' + 1) * pww[i]) % MOD;
}
H1[N - 1] = (s[N - 1] - 'a' + 1);
int j = 1;
for(int i = N - 2; i >= 0; i--) {
H1[i] = (H1[i + 1] + 1LL * (s[i] - 'a' + 1) * pww[j]) % MOD;
j++;
}
int cnt = N;
// for(int i = 0; i < N; i++) {
// cout << H1[i] << ' ';
// }
// cout << '\n';
for(int i = 0; i < N; i++) {
int st = 1, dr = min(i, N - i);
int best = 0;
while(st <= dr) {
int mid = (st + dr) / 2;
if(hash2(mid, i)) {
st = mid + 1;
best = mid;
}
else dr = mid - 1;
}
cnt += best;
//cout << i << ' ' << best << ' ' << "par" << '\n';
st = 1, dr = min(i, N - i - 1);
best = 0;
while(st <= dr) {
int mid = (st + dr) / 2;
if(hash1(mid, i)) {
st = mid + 1;
best = mid;
}
else dr = mid - 1;
}
cnt += best;
//cout << i << ' ' << best << ' ' << "impar" << '\n';
}
cout << cnt;
}