Cod sursa(job #2566674)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 2 martie 2020 23:09:37
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
ifstream in ("pscpld.in");
ofstream out("pscpld.out");
string s;
int n, rez;
int main()
{
    in>>s;
    n=s.size();
    vector <int> d1(n);
    for(int i=0, l=0, r=-1; i<n; i++)
    {
        int strt=(i>r) ? 1 : min(r-i+1, d1[l+r-i]);
        while(i+strt<n&&i-strt>=0&&s[i+strt]==s[i-strt])
            strt++;
        d1[i]=(--strt);
        if(r>i+strt)
            l=i-strt, r=i+strt;
        rez+=d1[i]+1;
        //cout<<d1[i]<<" ";
    }
    //cout<<"\n\n";
    vector <int> d2(n);
    for(int i=1, l=0, r=-1; i<n; i++)
    {
        int strt=(i>r) ? 0 : min(r-i+1, d2[l+r-i+1]);
        while(i+strt<n&&i-strt-1>=0&&s[i+strt]==s[i-strt-1])
            strt++;
        d2[i]=(--strt);
        if(r>i+strt)
            l=i-strt-1, r=i+strt;
        rez+=d2[i]+1;
        //cout<<d2[i]<<" ";
    }
    out<<rez;
    return 0;
}