Cod sursa(job #2857924)

Utilizator puica2018Puica Andrei puica2018 Data 26 februarie 2022 17:20:58
Problema PScPld Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

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

string s;
vector <char> a;
int n,cnt[1000005];
int c,dr;

int main()
{
    fin>>s;
    n=s.size();
    a.push_back('$');
    for(int i=0; i<n; i++)
    {
        a.push_back(s[i]);
        a.push_back('$');
    }
    for(int i=0; i<a.size(); i++)
    {
        if(dr>i)
            cnt[i]=min(cnt[2*c-i],dr-i);
        while(i+cnt[i]<a.size() && i-cnt[i]>=0 && a[i+cnt[i]]==a[i-cnt[i]])
            cnt[i]++;
        if(i+cnt[i]-1>dr)
        {
            dr=i+cnt[i]-1;
            c=i;
        }
    }
    long long ans=n;
    for(int i=0; i<a.size(); i++)
        ans+=(cnt[i]-1)/2;
    fout<<ans<<"\n";
    return 0;
}