Cod sursa(job #1179227)

Utilizator teoionescuIonescu Teodor teoionescu Data 28 aprilie 2014 11:30:18
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<fstream>
#include<string>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int Nmax = 1000001;
string s,S;
int P[2*Nmax],Add[2*Nmax];
int main(){
    in>>s;
    for(int i=0;i<s.size();i++) S+='#',S+=s[i]; S+="#$";
    int C=0,R=0;
    for(int i=0;i<S.size();i++){
        int j=2*C-i;
        if(R>i) P[i]=min(R-i, P[j]);
        while (S[i+1+P[i]]==S[i-1-P[i]]) P[i]++;
        if (i+P[i]>R) C=i , R=i+P[i];
    }
    long long Many=s.size();
    for(int i=0;i<S.size();i++) Many+=P[i]-P[i]/2-P[i]%2;
    out<<Many<<'\n';
    return 0;
}