Cod sursa(job #2575537)

Utilizator FrostfireMagirescu Tudor Frostfire Data 6 martie 2020 14:12:22
Problema PScPld Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>
#define NMAX 1000000

using namespace std;

ifstream f("pscpld.in");
ofstream g("pscpld.out");

int v[NMAX+10], sol;
string s, t;

int main()
{
    f >> s;
    t = '&';
    for(int i=0; i<s.size(); i++) t = t + '#' + s[i];
    t = t + '#' + '%';
    int C = 0, R = 0;
    for(int i=1; i<t.size()-1; i++)
        {   int ogl = 2 * C - i;
            if(i <= R) v[i] = min(R-i, v[ogl]);
            while(t[i+v[i]+1] == t[i-v[i]-1]) v[i]++;
            if(i + v[i] > R)
                {   C = i;
                    R = v[i] + i;
                }
        }
    for(int i=0; i<t.size(); i++)
        if(v[i] > 0) sol = sol + (v[i] - 1) / 2 + 1;
    g << sol << '\n';
    return 0;
}