Cod sursa(job #2489311)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 8 noiembrie 2019 14:39:13
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <cstring>

using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int mij,rasp,n,st,j,j2,dr,k = -1;
int v[2000005];
char s[2000005],s2[1000001];
int main()
{
    f.getline(s2,1000001);
    n = strlen(s2);
    n *= 2;
    for(int i = 0; i <= n; i += 2)
    {
        s[i] = '*';
        s[i + 1] = s2[++k];
    }
    for(int i = 1; i <= 2 * n; ++i)
    {
        if(i <= dr)
        {
            mij = st + dr - i;
            v[i] = min(v[mij],mij - st + 1);
            j = i + v[i];
            j2 = i - v[i];
            while(j2 >= 0 && j <= n && s[j] == s[j2])
            {
                j++;
                j2--;
                v[i]++;
            }
            if(dr < i + v[i] - 1)
            {
                dr = i + v[i] - 1;
                st = i - v[i] + 1;
            }
        }
        else
        {
            j = i;
            j2 = i;
            while(j2 >= 0 && j <= n && s[j] == s[j2])
            {
                j++;
                j2--;
                v[i]++;
            }
            dr = i + v[i] - 1;
            st = i - v[i] + 1;
        }
        rasp += v[i] / 2;
    }
    g << rasp;
    return 0;

}