Cod sursa(job #1172306)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 17 aprilie 2014 12:02:45
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");

char ss[2000010],s[1000001];
int p[2000010],n,maxi;
long long total;

// Manacher - retinem pe parcurs palindromul care se intinde cel mai mult inspre dreapta. La punctul curent, stim ca subsecventa inclusa in palindromul maxim este cel putin la fel de mare ca palindromul maximal din partea opusa a palindromului maxim care este inclusa in palindromul maxim

int main()
{
    fin>>(ss+1);

    int t = strlen (ss+1);

    s[n=1] = '0';

    for (int i=1; i<=t; ++i)
    {
        s[++n] = ss[i];
        s[++n] = '0';
    }

    //Reducem problema doar la siruri impare, introducand 0 intre fiecare nuamr

    for (int i=1; i<=n; ++i)
    {
        int current;

        if (i != 1)
            current = min (p[2*maxi-i],2*maxi-i - (maxi-p[maxi]));
        else current = 1;

        for (; i+current<=n && i-current >=1; ++current)
        {
            if (s[i+current] != s[i-current])
                break;
        }

        total += current/2;
        p[i] = current;

        if (p[i] + i - 1 > p[maxi] + maxi -1)
            maxi = i;
    }

    fout<<total;
}