Cod sursa(job #2539229)

Utilizator Vlad.Vlad Cristian Vlad. Data 5 februarie 2020 19:12:01
Problema PScPld Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <iostream>
#define NMAX 2 * 1000000 + 5
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string strR, str = "";
int N;
long long L[NMAX];
void read() {
    fin >> strR;
    for (int i = 0; i < strR.length(); ++i) {
        str += "!!";
        str[2 * i + 1] = strR[i];
    }
    str += "!";
    N = str.length();
}
void manacher() {
    int right = 2, center = 1, simi;
    long long dist;
    bool expand;
    L[0] = L[N] = 0;
    L[1] = 1;
    for (int i = 2; i <= N; ++i) {
        simi = 2 * center - i;
        bool expand = false;
        dist = right - i;
        if (dist >= 0) {
            if (L[simi] < dist || i == N - 1) {
                L[i] = L[simi];
            }
            else {
                L[i] = min(L[simi], dist);
                expand = true;
            }
        }
        else {
            L[i] = 0;
            expand = true;
        }
        if (expand) {
            while ((i + L[i]) < N && (i - L[i]) > 0 && str[i + L[i] + 1] == str[i - L[i] - 1]) {
                L[i]++;
            }
        }
        if (i + L[i] > right) {
            center = i;
            right = i + L[i];
        }
    }
}
int main()
{
    read();
    manacher();
    long long sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += (L[i] / 2);
        if (i & 1) {
            sum++;
        }
    }
    fout << sum << "\n";
    return 0;
}