Cod sursa(job #1097512)

Utilizator tudorv96Tudor Varan tudorv96 Data 3 februarie 2014 15:36:26
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <string>
#include <fstream>
#include <iostream>
using namespace std;

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

const int N = 2e6 + 5;

string Input, s;
int Len[2][N], n;
long long sol;

int expand(int st, int dr) {
    int sol = 0;
    while (st && dr <= n && s[st] == s[dr])
        st--, dr++, sol++;
    return sol;
}

void Manacher_Odd() {
    int best = 0, poz = 0;
    for (int i = 1; i <= n; ++i) {
        if (best >= i)
            Len[0][i] = min(Len[0][2 * poz - i], best - i);
        int st = i - Len[0][i], dr = i + Len[0][i];
        Len[0][i] += expand(st, dr);
        if (i + Len[0][i] > best) {
            best = Len[0][i] + i;
            poz = i;
        }
        sol += 1LL * Len[0][i];
    }
}

void Manacher_Even() {
    int best = 0, poz = 0;
    for (int i = 1; i <= n; ++i) {
        if (s[i] != s[i+1])
            continue;
        if (best >= i)
            Len[1][i] = min(Len[1][2 * poz - i], best - i - 1);
        int st = i + Len[1][i], dr = i + 1 + Len[1][i];
        Len[1][i] += expand(st, dr);
        if (i + 1 + Len[1][i] > best) {
            best = i + 1 + Len[1][i];
            poz = i;
        }
        sol += 1LL * Len[1][i];
    }
}

int main() {
    fin >> Input;
    s = " " + Input;
    n = s.size() - 1;
    Manacher_Odd();
    Manacher_Even();
    fout << sol;
}