Cod sursa(job #1975063)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 29 aprilie 2017 20:09:53
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstring>
#include <fstream>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;

ifstream in("pscpld.in");
ofstream out("pscpld.out");

int palindromeCreation(string& S) {
    vector<char> aux;
	vector<int>Manacher;
    aux.push_back('*');
	for(int i=0;i<S.size();i++)
    {
        aux.push_back(S[i]);
        aux.push_back('*');
    }
	Manacher.push_back(0);
    int r=0,c=0;
    for(int i=1;i<aux.size();i++)
    {
		if(i<=r)
		{
			int a=2*c-i;
			int len=min(Manacher[a],r-i);
			if(i+len==r)
				while(i-len-1>=0&&i+len+1<aux.size()&&aux[i+len+1]==aux[i-len-1])
					r++,len++,c=i;
			Manacher.push_back(len);
		}
		else
		{
			int l=0;
			c=i,r=i;
			while(i-l-1>=0&&i+l+1<aux.size()&&aux[i-l-1]==aux[i+l+1])
				l++,r++;
			Manacher.push_back(l);
		}
    }
	long long ans=0;
	for(int i=0;i<aux.size();i++)
	ans+=1LL*(Manacher[i]+1)/2;
	return ans;
}
   
int main() {
    string S;
    in >> S;
    out << palindromeCreation(S) << "\n";
    return 0;
}