Cod sursa(job #1673491)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 3 aprilie 2016 21:13:41
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<bitset>
#include<algorithm>
#include<cstring>

using namespace std;

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

int const NMax = 1000005;
int L[2*NMax];
char A[NMax], aux[NMax];
int n, dr, center;
long long sol;

void Read()
{
    A[0] = '*';
    f.getline(aux, 1000005);
    strcat(A, aux);
    n = strlen(A) - 1;
}

void Solve()
{
    int i, mid, low, up, j;

    for(i=1; i<=2*n-1; i++){
        if(dr > i+1){
            if(i % 2){
                mid = i/2 + 1;
                L[i] = min(L[2*center - i], dr - i);
                for(j = L[i]/2 + 1; A[mid + j] == A[mid - j]; j++)
                    L[i] += 2;
            }
            else{
                low = i/2;
                up = i/2 + 1;
                L[i] = min(L[2*center - i], dr - i);
                for(j = L[i]/2; A[low - j] == A[up + j]; j++)
                    L[i] += 2;
            }
            if(i + L[i] > dr){
                dr = i + L[i];
                center = i;
            }
        }
        else{
            if(i % 2){
                mid = i/2 + 1;
                L[i] = 1;
                for(j=1; A[mid + j] == A[mid - j]; j++)
                    L[i] += 2;
            }
            else{
                low = i/2;
                up = i/2 + 1;
                for(j=0; A[low - j] == A[up + j]; j++)
                    L[i] += 2;
            }

            dr = i + L[i];
            center = i;
        }
        sol += (L[i]+1)/2;
    }

    g<<sol<<"\n";
}

int main()
{
    Read();
    Solve();
    return 0;
}