Cod sursa(job #2654345)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 30 septembrie 2020 16:24:56
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <cstring>

using namespace std;

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

char v[1000000];
int d1[1000000],d2[1000000],n;

int trivial(int k, int i)
{
    while(v[i-k]==v[i+k]&&i-k>=0&&i+k<n)
        k++;
    return k;
}

int mn(int a, int b)
{
    return a>b?b:a;
}

int main()
{
    f>>v;
    n=strlen(v);
    int l1=0,l2=0,r2=-1,r1=-1,s=0;
    for(int i=0;i<n;i++)
    {
        int k=(i>r1)?1:mn(d1[l1+r1-i],d1[l1+r1-i]-r1+i);
        d1[i]=trivial(k,i);
        s+=d1[i];
        if(i+d1[i]>r1) {l1=i-d1[i]+1; r1=i+d1[i]-1;}
        k=(i>r2)?0:mn(d2[l2+r2-i+1],r2+i-1);
        while (0 <= i - k - 1 && i + k < n && v[i - k - 1] == v[i + k]) {
        k++;
        }
        d2[i] = k--;
        if (i + k > r2) {
            l2 = i - k - 1;
            r2 = i + k ;
        }
        s+=d2[i];
    }
    g<<s;
    return 0;
}