Pagini recente » Cod sursa (job #1270637) | Cod sursa (job #798658) | Cod sursa (job #1887174) | Cod sursa (job #1912745) | Cod sursa (job #2466891)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int main() {
string s;
cin>>s;
long long int total = 0;
vector<int> e(s.size(), 0), o(s.size(), 0);
for(int i = 0, l = -1, r = -1; i < s.size(); i++) {
int ex = 1;
if(i <= r) {
ex = min(r - i + 1, o[l + r - i]);
}
while((s[i - ex] == s[i + ex]) && ((i + ex) < s.size()) && ((i - ex) >= 0)) {
ex++;
}
o[i] = ex--;
if((i + ex) > r) {
l = i - r;
r = i + ex;
}
}
for(int i = 0, l = -1, r = -1; i < s.size(); i++) {
int ex = 0;
if(i <= r) {
ex = min(r - i + 1, e[l + r - i + 1]);
}
while((s[i - ex - 1] == s[i + ex]) && ((i + ex) < s.size()) && ((i - ex - 1) >= 0)) {
ex++;
}
e[i] = ex--;
if((i + ex) > r) {
l = i - r - 1;
r = i + ex;
}
}
total += accumulate(o.begin(), o.end(), 0LL);
total += accumulate(e.begin(), e.end(), 0LL);
cout<<total<<'\n';
return 0;
}