Cod sursa(job #2910920)

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

#define N 1000005

using namespace std;

ifstream fin("pscpld.in");

ofstream fout("pscpld.out");

int n,d[2*N],l,r;

long long ct;

char s[2*N],t[2*N];

long long Manacher()

{

       fin>>t;

    s[0]='%';

    for(int i=0;t[i];i++)

    {

        s[++n]='#';

        s[++n]=t[i];

    }

    s[++n]='#';
    for(int i=1;i<=n;i++)

    {

        if(i<=r)d[i]=min(r-i+1,d[l+(r-i)]);

        while(i>d[i] &&i+d[i]<=n&&s[i-d[i]]==s[i+d[i]]) d[i]++;

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

    }

    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;

    //string t;

  //  for(auto c:s) t+=string("#")+c;

    fout<<Manacher();

    return 0;

}