Pagini recente » Cod sursa (job #2547048) | Cod sursa (job #2495963) | Cod sursa (job #1032366) | Cod sursa (job #1298437) | Cod sursa (job #2036597)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
const long long BASE = 227;
const long long MOD = 77007001;
void Make(string &in_str, string &s) {
for (auto x : in_str) {
s += x;
s += '$';
}
}
void Init(string &s, vector < long long > &Hash_st, vector < long long > &Hash_dr,
vector < long long > &Base_pow) {
for (int i = 0; i < s.size(); i ++) {
if (not i) {
Hash_st[0] = 1ll * s[0];
continue;
}
Hash_st[i] = (Hash_st[i - 1] * BASE + 1ll * s[i]) % MOD;
}
for (int i = s.size() - 1; i >= 0; i --) {
if (i == s.size() - 1) {
Hash_dr[i] = 1ll * s[s.size() - 1];
continue;
}
Hash_dr[i] = (Hash_dr[i + 1] * BASE + 1ll * s[i]) % MOD;
}
Base_pow[0] = 1ll;
for (int i = 1; i <= s.size(); i ++) {
Base_pow[i] = (Base_pow[i - 1] * BASE) % MOD;
}
}
void poz(long long &x) {
if (x < 0) {
x += MOD;
}
}
void Solve(vector < long long > &Hash_st, vector < long long > &Hash_dr,
vector < long long > &Base_pow, vector < int > &how_many, string &s) {
int len = s.size();
for (int i = 0; i < len; i ++) {
if (i == 0 or i == len - 1) {
how_many[i] = (s[i] == '$' ? 0 : 1);
continue;
}
int ans = 0;
int left = 0;
int right = min(len - i - 1, i);
while (left <= right) {
int cur_len = (left + right) >> 1;
long long l_H = Hash_st[i - 1];
if (i > cur_len) {
l_H -= (Hash_st[i - 1 - cur_len] * Base_pow[cur_len]) % MOD;
}
long long r_H = Hash_dr[i + 1] - ((Hash_dr[i + 1 + cur_len] * Base_pow[cur_len]) % MOD);
poz(r_H);
poz(l_H);
if (l_H == r_H) {
ans = cur_len;
left = cur_len + 1;
continue;
}
right = cur_len - 1;
}
if (i % 2 == 0) {
how_many[i] = 1 + ans / 2;
}
else {
how_many[i] = (ans + 1) / 2;
}
}
}
int main() {
string in_str, s;
cin >> in_str;
Make(in_str, s);
vector < long long > Hash_st(s.size() + 7);
vector < long long > Hash_dr(s.size() + 7);
vector < long long > Base_pow(s.size() + 7);
Init(s, Hash_st, Hash_dr, Base_pow);
vector < int > how_many(s.size() + 7);
Solve(Hash_st, Hash_dr, Base_pow, how_many, s);
long long sol = 0;
for (int i = 0; i < s.size(); i ++) {
sol += 1ll * how_many[i];
}
cout << sol << '\n';
}