Cod sursa(job #2611589)

Utilizator CharacterMeCharacter Me CharacterMe Data 7 mai 2020 10:18:17
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
typedef long long ll;

ll sol;
int n, center = 1;
string s, obj;
int manacher[1000005];

int main()
{

    fin >> s;
    n = s.length();

    obj += '#';
    for(int i = 0; i < n; ++i){
        obj += s[i];
        obj += '#';
    }

    n = obj.length();
    manacher[0] = 0;
    manacher[1] = 1;

    for(int i = 2; i < n; ++i){

        int mirror = 2 * center - i;
        if(mirror - manacher[mirror] > center - manacher[center]){
            manacher[i] = manacher[mirror];
        }
        else{
            if(mirror >= center - manacher[center]) manacher[i] = manacher[mirror];

            int lft = i - manacher[i] - 1;
            int rgt = i + manacher[i] + 1;

            while(lft >= 0 && rgt < n){
                if(obj[lft] == obj[rgt]) ++manacher[i];
                else break;

                --lft; ++rgt;
            }

            if(i + manacher[i] > center + manacher[center])
                center = i;

        }

        sol = sol + 1LL * (manacher[i] + 1) / 2LL;

    }

    fout << sol + 1;

    return 0;
}