Cod sursa(job #3292830)

Utilizator tedicTheodor Ciobanu tedic Data 9 aprilie 2025 14:12:55
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;
string s,suport="";
int L[2000005];
long long manacher()
{
    long long best=0,ans=0;
    for(int i=1; i<suport.size()-1; i++)
    {
        int rightBound=best+L[best];
        if(rightBound>i)
            L[i]=min(rightBound-i, L[2*best-i]);
        while(i+L[i]+1<suport.size() && i-L[i]-1>=0 && suport[i+L[i]+1]==suport[i-L[i]-1])
            L[i]++;
        if(i+L[i]>rightBound)
            best=i;
        ans+=(L[i]+1)/2;
    }
    return ans;
}
int main()
{
    ifstream cin("pscpld.in");
    ofstream cout("pscpld.out");
    cin>>s;
    suport+='#';
    for(int i=0; i<s.size(); i++)
        suport+=s[i], suport+='#';
    cout<<manacher();
    return 0;
}