Pagini recente » Cod sursa (job #3343688) | Cod sursa (job #3305958) | Cod sursa (job #3323389) | Cod sursa (job #3302553) | Cod sursa (job #3306603)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main() {
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string original;
fin >> original;
string sir;
for(auto c: original) {
sir.push_back('#');
sir.push_back(c);
}
sir.push_back('#');
int mx = 0, cmx = 0, pal = 0;
vector<int> r(sir.size());
for(int i=0; i<sir.size(); ++i) {
int raza = 0;
if(i < mx) {
raza = r[cmx - (i - cmx)];
}
for(; i-raza >= 0 && i+raza < sir.size() && sir[i-raza] == sir[i+raza]; ++raza);
--raza;
if(i+raza > mx) {
mx = i+raza;
cmx = i;
}
r[i] = raza;
pal += (raza + 1) / 2;
}
fout << pal << '\n';
return 0;
}