Cod sursa(job #3041645)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 31 martie 2023 21:47:44
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

///#include <tryhardmode>
///#include <GODMODE::ON>

///YOU KNOW IT'S NOT THE SAME
///AS IT WAS...

using namespace std;

#define cin fin
#define cout fout

ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");

const int NMAX=2e6+5;
int dp[NMAX];

string a;
string s;

int main()
{
    int n,i,j,st=0,dr=0,dist=0;
    long long kon=0;
    cin>>a;
    n=a.size();
    s.push_back('*');
    for(i=0;i<n;i++)
    {
        s.push_back(a[i]);
        s.push_back('*');
    }
    n=s.size();
    for(i=0;i<n;i++)
    {
        if(i>dr)
            dist=1;
        if(i<=dr)
            dist=min(dp[st+dr-i],dr-i+1);
        while(i+dist<n)
        {
            if(i-dist<0)
                break;
            if(s[i+dist]!=s[i-dist])
                break;
            dist++;
        }
        dp[i]=dist;
        if(dr<i+dist-1)
        {
            st=i-dist+1;
            dr=i+dist-1;
        }
    }
    for(i=0;i<n;i++)
        kon+=dp[i]/2;
    cout<<kon;
    return 0;
}