Cod sursa(job #2638888)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 30 iulie 2020 14:27:37
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

const int DIM = 1000005;

int n,A[DIM],B[DIM];

long long ans=0;

char S[DIM];

void Read()
{
    while(fin>>S[n])
        n++;
}

void Manacher()
{
    int l=0,r=-1;
    for(int i=0;i<n;i++)
    {
        int k=1;
        if(i<=r)
            k=min(A[l+r-i],r-i+1);
        while(i-k>=0 && i+k<n && S[i-k]==S[i+k])
            k++;
        A[i]=k;
        k--;
        if(i+k>r)
        {
            l=i-k;
            r=i+k;
        }
    }
    l=0,r=-1;
    for(int i=0;i<n;i++)
    {
        int k=0;
        if(i<=r)
            k=min(B[l+r-i+1],r-i+1);
        while(i-k-1>=0 && i+k<n && S[i-k-1]==S[i+k])
            k++;
        B[i]=k;
        k--;
        if(i+k>r)
        {
            l=i-k-1;
            r=i+k;
        }
    }
}

void Print()
{
    for(int i=0;i<n;i++)
        ans+=A[i];
    for(int i=0;i<n;i++)
        ans+=B[i];
    fout<<ans<<'\n';
}

int main()
{
    Read();
    Manacher();
    Print();
}