Cod sursa(job #2461064)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 24 septembrie 2019 20:52:20
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define NMAX 1000000
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
long long v[2*NMAX+100], sol;
string s1;
vector <char> s;
int main()
{
    f >> s1;
    int n1 = s1.size();
    s.push_back('@');
    for(int i=0; i<n1; i++)
        {   s.push_back('#');
            s.push_back(s1[i]);
        }
    s.push_back('#');
    s.push_back('%');
    int n = s.size();
    long long C=0, R=0;
    for(int i=1; i<n-1; i++)
        {   long long 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<n; i++) sol = sol + v[i]/2;
    g << sol + n1 << '\n';
    return 0;
}