Cod sursa(job #1969572)

Utilizator tudi98Cozma Tudor tudi98 Data 18 aprilie 2017 15:33:39
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;

#define REP(i,a) for (int i = 0; i < a; i++)
#define FOR(i,a,b) for (int i = a; i <= b; i++)
#define ROF(i,a,b) for (int i = a; i >= b; i--)
#define FOREACH(it,x) for (auto it: (x))
#define pb push_back
#define SZ(x) ((int)(x).size())

char text[1000005];
int p[2][1000005];
int n;

void Manacher()
{
    int l = -1,r = -1;;
    REP(i,n) {      /// odd length
        if (r < i) p[1][i] = 1;
        else p[1][i] = min(r - i + 1, p[1][l+r-i]);
        int L = i - p[1][i] + 1, R = i + p[1][i] - 1;
        while (L-1 >= 0 && R+1 < n && text[L-1] == text[R+1]) L--,R++,p[1][i]++;
        if (R > r) r = R,l = L;
    }
    l = -1,r = -1;
    REP(i,n) {     /// even length
        if (r < i) p[0][i] = 0;
        else p[0][i] = min(r - i + 1, p[0][l+r-i+1]);
        int L = i - p[0][i], R = i + p[0][i] - 1;
        while (L-1 >= 0 && R+1 < n && text[L-1] == text[R+1]) L--,R++,p[0][i]++;
        if (R > r) r = R,l = L;
    }
}

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

    fin >> text;   n = strlen(text);
    Manacher();
    long long sol = 0;
    REP(i,n) sol += p[1][i] + p[0][i];
    fout << sol;
}