Cod sursa(job #2465503)

Utilizator RadianElevenAdrian Ariotn RadianEleven Data 30 septembrie 2019 11:01:16
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 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;
}