Pagini recente » Cod sursa (job #568163) | Cod sursa (job #1199951) | Cod sursa (job #2770395) | Cod sursa (job #1023260) | Cod sursa (job #1975794)
#include <bits/stdc++.h>
using namespace std;
vector<int> pscpld(const string& str){
const int n = str.size();
vector<int> v(n, 0);
for(int i = 0, mij = -1, dr = -1; i < n; ++i){
for(v[i] = (dr <= i ? 0 : min(v[2*mij - i], dr-i));
i+v[i]+1 < n && i-v[i]-1 >= 0 && str[i+v[i]+1] == str[i-v[i]-1];
++v[i]);
if(i+v[i] > dr) mij = i, dr = i+v[i]; }
return v; }
string intersperse(const string& str){
string rez = "@";
for(const auto x : str){
rez.push_back(x);
rez.push_back('@'); }
return rez; }
int main(){
ifstream f("pscpld.in");
ofstream g("pscpld.out");
string str;
f >> str;
str = intersperse(str);
const auto pal_len = pscpld(str);
g << accumulate(begin(pal_len), end(pal_len), 0ll,
[](const long long x, const long long y){ return x + (y+1)/2ll; }) << endl;
return 0; }