Cod sursa(job #3275883)

Utilizator unomMirel Costel unom Data 11 februarie 2025 21:24:53
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>

using namespace std;

ifstream in("pscpld.in");
ofstream out("pscpld.out");
int n, ans;
string init, s;
int man[2000005];

int main()
{
    in>>init;

    for(auto it: init)
    {
        s += string("#") + it;
    }
    s += string("#");

    n = s.size();
    s = '$' + s + '^';

    int l = 1;
    int r = 1;
    for(int i = 1; i<=n; i++)
    {
        man[i] = max(0, min(r - i, man[l + (r - i)]));

        while(s[i - man[i]] == s[i + man[i]])
        {
            man[i]++;
        }

        if(i + man[i] > r)
        {
            l = i - man[i];
            r = i + man[i];
        }

        if(i != 1 && i != n)
        {
            if(s[i] == '#')
            {
                ans += (man[i] - 1) / 2;
            }
            else
            {
                ans += man[i] / 2;
            }
        }
    }

    /*for(int i = 1; i<=n; i++)
    {
        out<<s[i]<<" ";
    }
    out<<'\n';
    for(int i = 1; i<=n; i++)
    {
        out<<man[i]<<" ";
    }
    out<<'\n';*/

    out<<ans;

    return 0;
}