Cod sursa(job #2460867)

Utilizator FrostfireMagirescu Tudor Frostfire Data 24 septembrie 2019 17:01:42
Problema PScPld Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>
#include <iostream>
#include <string>
#define NMAX 1000000

using namespace std;

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

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

int main()
{
    f >> s1;
    s = '$';
    for(int i=0; i<s1.size(); i++) s = s + '#' + s1[i];
    s = s + '#' + '@';

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