Pagini recente » Profil Sho10 | Cod sursa (job #2456751) | Diferente pentru utilizator/stargold2 intre reviziile 110 si 111 | Cod sursa (job #417086) | Cod sursa (job #3196640)
#include <bits/stdc++.h>
#pragma GCC optimize ("03")
using namespace std;
#define INFILE "pscpld.in"
#define OUTFILE "pscpld.out"
typedef long long ll;
const int N_MAX = 1e6 + 5;
int palindrom[2 * N_MAX + 1];
void solve(){
string aux; cin >> aux;
string s;
for(auto &ch : aux){
s += '$';
s += ch;
}
s += '$';
int left = 0, right = 0;
for(int i = 0; i < s.size(); ++i){
if(i < right){
palindrom[i] = min(right - i + 1, palindrom[left + right - i]);
}
while(i - palindrom[i] >= 0 && i + palindrom[i] < s.size() && s[i - palindrom[i]] == s[i + palindrom[i]]){
palindrom[i]++;
}
if(i + palindrom[i] - 1 > right){
right = i + palindrom[i] - 1;
left = i - palindrom[i] + 1;
}
}
ll ans = 0;
for(int i = 0; i < s.size(); ++i){
ans += palindrom[i] / 2;
}
cout << ans << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
freopen(INFILE, "r", stdin);
freopen(OUTFILE, "w", stdout);
cin.tie(0), cout.tie(0);
solve();
return 0;
}