Pagini recente » Cod sursa (job #1595482) | Cod sursa (job #626655) | Cod sursa (job #2270712) | Clasament easy_choice | Cod sursa (job #2466898)
#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 = 0, 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 - ex;
r = i + ex;
}
}
for(int i = 0, l = 0, 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 - ex - 1;
r = i + ex;
}
}
for(int x = 0;x<s.size();x++){
total += e[x];
total += o[x];
}
cout<<total<<'\n';
return 0;
}