Pagini recente » Cod sursa (job #604538) | Cod sursa (job #1874700) | Cod sursa (job #1042719) | Cod sursa (job #62376) | Cod sursa (job #2466892)
#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;
}
}
for(int x = 0;x<s.size();x++){
total += e[x];
total += o[x];
}
cout<<total<<'\n';
return 0;
}