Cod sursa(job #2672854)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 15 noiembrie 2020 09:52:27
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>
#define NMAX 1000000
 
using namespace std;
 
ifstream f("pscpld.in");
ofstream g("pscpld.out");
 
long long n, v[2*NMAX+10], ans;
char s[2*NMAX+10];
string s1;
 
int main()
{
    f >> s1;
    int n1 = s1.size();
    s[++n] = '%';
    s[++n] = '#';
    for(int i=0; i<n1; i++)
        {   s[++n] = s1[i];
            s[++n] = '#';
        }
    s[++n] = '$';
    int C = 0, R = 0;
    for(int i=1; i<n; i++)
        {   int ogl = 2 * C - i;
            if(i < R) v[i] = min((long long)(R - i), v[ogl]);
            while(s[i+v[i]+1] == s[i-v[i]-1]) v[i]++;
            if(i + v[i] > R)
                {   C = i;
                    R = v[i] + i;
                }
        }
    for(int i=0; i<n; i++) ans = ans + (v[i] + 1) / 2;
    g << ans << '\n';
    return 0;
}