Cod sursa(job #1732437)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 21 iulie 2016 16:59:55
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <math.h>
#include <algorithm>
#include <string>

using namespace std;

string problemName = "pscpld";
string inFile = problemName+".in";
string outFile = problemName+".out";
ifstream fin(inFile.c_str());
ofstream fout(outFile.c_str());

const int N = 1e6+5;
string s,ax;
int p[2*N];


int main(){
    int n,i;
    fin>>ax;
    s += '@';
    s += '#';
    n = ax.size();
    for(i = 0;i < n;i++){
        s += ax[i];
        s += '#';
    }
    s += '$';
    int mirr,R,C;
    R = C = 0;
    n <<= 1;
    n++;
    long long unsigned sum = 0;
    for(i = 1;i <= n;i++){
        mirr = 2*C-i;
        if(R > i){
            p[i] = min(R-i, p[mirr]);
        }
        while(s[i+1+p[i]] == s[i-1-p[i]]){
            p[i]++;
        }
        if(i+p[i] > R){
            R = i + p[i];
            C = i;
        }
        sum += (p[i]+1)/2;
    }
    fout<<sum;
    return 0;
}