Cod sursa(job #2634824)

Utilizator Katherine456719Swan Katherine Katherine456719 Data 12 iulie 2020 13:38:54
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

int manacher[2000006];//retinem cat de mult ne putem duce in dreapta

int main()
{
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");
    string s,inits;
    fin >> inits;
    s="&&";
    for(auto x:inits)
    {
        s+=x;
        s+="&";
    }
    int mid=0;
    for(int i=1; i<s.size(); ++i)
    {
        if(mid + manacher[mid] >= i)//i se afla in interiorul palindromului
        {
            manacher[i]=min(manacher[mid-(i-mid)],mid + manacher[mid] - i);
            while(i + manacher[i] + 1 < s.size() and i - manacher[i] - 1 >=1 and s[i+manacher[i]+1]== s[i - manacher[i]-1])
                manacher[i]+=1;
            if(i + manacher[i] >= mid + manacher[mid])
                mid=i;
        }
        else
        {
            manacher[i]=0;
             while(i+manacher[i]+1 < s.size() and i-manacher[i]-1>=1 and s[i+manacher[i]+1]== s[i-manacher[i]-1])
                manacher[i]+=1;
            mid=i;
        }
    }
    long long ans=0;
    for(int i=1; i<s.size(); ++i)
        ans+=(manacher[i] + 1)/2;
    fout<<ans;
    return 0;
}