Cod sursa(job #2910923)

Utilizator mihneazzzMacovei Daniel mihneazzz Data 25 iunie 2022 20:08:44
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
	#include <bits/stdc++.h>

#define N 1000005

using namespace std;

ifstream fin("pscpld.in");

ofstream fout("pscpld.out");

int n,d[2*N];

long long ct;

char s[2*N];

long long Manacher(string s)

{


    int l=1,r=1;

    for(int i=1;i<=n;i++)

    {

        d[i]=max(0,min(r-i,d[l+(r-i)]));

        while(s[i-d[i]]==s[i+d[i]]) d[i]++;

        if(i+d[i]>r) l=i-d[i],r=i+d[i];

    }

    for(int i=1;i<=n;i++) ct+=d[i]/2;

    ///for(int i=1;i<=n;i++) cout<<d[i]<<" ";

    return ct;

}

int main()

{

    fin>>s;

    char t[2*N];
	t[0]='$';
    for(int i=0;s[i];i++) t[++n]='#',t[++n]=s[i];
    t[++n]='#';
    fout<<Manacher(t);

    return 0;

}