Cod sursa(job #2910917)

Utilizator mihneazzzMacovei Daniel mihneazzz Data 25 iunie 2022 19:43:28
Problema PScPld Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 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;

string s;

long long Manacher(string s)

{

    n=s.size();

    s="$"+s;

    int l=0,r=0;

    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]>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(t+"#");

    return 0;

}