Cod sursa(job #2465717)

Utilizator AnduebossAlexandru Ariton Andueboss Data 30 septembrie 2019 18:44:34
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

long long vek[2000100], sol;
string s1;
string s;

long long  l,r;

int main()
{
    f>>s1;
    int siz=s1.size();
    s.push_back('$');
    for(int i=0;i<siz;i++){
        s.push_back('#');
        s.push_back(s1[i]);
    }
    s.push_back('#');
    s.push_back('%');
    int n=s.size();
    for(int i=1;i<n;i++) {
        long long ras=2*l-i;
        if(i<=r)
            vek[i]=min(r-i, vek[ras]);
        while(s[i+vek[i]+1] == s[i-vek[i]-1])
            vek[i]++;
        
        if(vek[i]+i>r) {
            l=i;
            r=vek[i]+i;
        }
    }
    for(int i=0;i<n;i++) sol=sol+vek[i]/2;
    g<<sol+siz;
    return 0;
}