Pagini recente » Cod sursa (job #809287) | Cod sursa (job #1345510) | Cod sursa (job #1397210) | Cod sursa (job #2522365) | Cod sursa (job #1426623)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
int gaseste_nr_palindroame(const string& str){
class Container{
const string& str;
public:
constexpr Container(const string& s):
str(s){}
constexpr char operator[](const int x)const{
return (x&1) ? str[x/2] : '#'; } } v(str);
const int n = 2*str.size()+1;
int rez = str.size();
vector<int> marime_palind(n, 0);
int citit_pana_la = -1;
for(int i = 0; i < n; ++i){
citit_pana_la = max(i, citit_pana_la);
if(i+marime_palind[i] >= citit_pana_la){
int j = citit_pana_la-i;
while(i-j >= 0 && i+j < n && v[i-j] == v[i+j]){
marime_palind[i+j] = marime_palind[i-j];
citit_pana_la = max(citit_pana_la, i+j);
++j; }
marime_palind[i] = j-1; }
rez += marime_palind[i]/2; }
return rez; }
int main(){
ifstream f("pscpld.in");
ofstream g("pscpld.out");
string str;
f >> str;
g << gaseste_nr_palindroame(str);
return 0; }