Cod sursa(job #2634816)

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

using namespace std;

int manacher[2000006];//retinem lungimea

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]-1)/2 >= i)//i se afla in interiorul palindromului
        {
            manacher[i]=min(manacher[mid-(i-mid)],2*(mid +(manacher[mid]-1)/2-i)+1);
            while(i+(manacher[i]-1)/2+1 < s.size() and i-(manacher[i]-1)/2-1>=1 and s[i+(manacher[i]-1)/2+1]== s[i-(manacher[i]-1)/2-1])
                manacher[i]+=2;
            if(i+(manacher[i]-1)/2 >= mid + (manacher[mid]-1)/2)
                mid=i;
        }
        else
        {
            manacher[i]=1;
             while(i+(manacher[i]-1)/2+1 < s.size() and i-(manacher[i]-1)/2-1>=1 and s[i+(manacher[i]-1)/2+1] == s[i-(manacher[i]-1)/2-1])
                manacher[i]+=2;
            mid=i;
        }
    }
    long long ans=0;
    for(int i=1; i<s.size(); ++i)
        ans+=((manacher[i]-1)/2+1)/2;
    fout<<ans;
    return 0;
}