Cod sursa(job #940608)

Utilizator SteveStefan Eniceicu Steve Data 16 aprilie 2013 19:03:24
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>

using namespace std;

int N;
char s[1000011];
char v[2000011];
int dp[2000011];

void Citire ()
{
    ifstream fin ("pscpld.in");
    fin >> s;
    for (N = 0; s[N] != '\0'; N++)
    {
        v[N << 1] = s[N];
        v[(N << 1) + 1] = '$';
    }
    N = (N << 1) - 1;
    v[N] = '\0';
    fin.close ();
}

long long Business ()
{
    long long S = 0;
    dp[0] = 0;
    int poz = 0, curent;
    for (int i = 1; i < N; i++)
    {
        if (i >= poz + dp[poz])
        {
            curent = 1;
            for (; i + curent < N && i - curent >= 0; curent++)
                if (v[i + curent] != v[i - curent]) break;
            curent--;
        }
        else
        {
            curent = min (dp[(poz << 1) - i], poz + dp[poz] - i);
            if (i + curent == poz + dp[poz])
            {
                for (++curent; curent < N && i - curent >= 0; curent++)
                    if (v[i + curent] != v[i - curent]) break;
                curent--;
            }
        }
        dp[i] = curent;
        if (i + dp[i] >= poz + dp[poz]) poz = i;
        if (v[i] != '$') S += dp[i] >> 1;
        else S += (dp[i] + 1) >> 1;
    }
    return S + (N >> 1) + 1;
}

void Scriere ()
{
    ofstream fout ("pscpld.out");
    fout << Business ();
    fout.close ();
}

int main ()
{
    Citire ();
    Scriere ();
    return 0;
}