Cod sursa(job #1977032)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 4 mai 2017 21:19:18
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <cstring>
#define Nmax 2000005
#define LL long long

using namespace std;

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

int n,lg[Nmax];
LL rez;
char s[Nmax],s2[Nmax];

int main()
{
    f>>s+1;
    n = strlen(s+1);

    int nr = 1;
    for (int i=1;i<=n;i++)
    {
        s2[i*2-1] = '*';
        s2[i*2] = s[i];
    }
    n = n*2+1;
    s2[n] = '*';

    int index = 0,c;
    for (int i=1;i<=n;i++)
    {
        if (i<index)
        {
            lg[i] = min(index - i + 1, lg[c - (i-c)]);
        }
        while (i-lg[i]>=1 && i+lg[i]<=n && s2[i-lg[i]]==s2[i+lg[i]])
            lg[i]++;
        rez += lg[i]/2;
        if (i+lg[i]>index)
        {
            index  = i+lg[i]-1;
            c = i;
        }
    }

    g<<rez;

    return 0;
}