Cod sursa(job #2784181)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 16 octombrie 2021 00:09:59
Problema PScPld Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s;
int n;
int dp[1000005];

void manacher()
{
    if (n < 2){
        dp[1] = 1;
        return;
    }

    string s2 = "#";
    for (int i=0;i<n;i++){
        s2.push_back(s[i]);
        s2.push_back('#');
    }

    int cx = 0, mx = 0;
    const int n2 = 2 * n + 1;

    for (int i=1;i<n2;i++){
        int j = 0;
        if (i >= mx){
            j = i + 1;
        }else{
            int ii = 2 * cx - i;
            dp[i] = min(mx - i, dp[ii]);
            if (ii - dp[ii] <= cx - dp[cx]){
                j = mx + 1;
            }
        }

        while(j && (j < n2) && (2 * i - j >= 0) && (s2[j] == s2[2*i-j]))
            dp[i] ++, j ++;

        if (i + dp[i] > mx)
            mx = i + dp[i], cx = i;

    }


    /*for (int i=0;i<n2;i++)
        fout << dp[i] << ' ';

    fout << '\n';

    for (int i=0;i<n2;i++)
        fout << s2[i] << ' ';
    fout << '\n';*/
    long long suma = 0;
    for (int i=0;i<n2;i++){
        suma += (dp[i] + 1) / 2;
    }
    fout << suma << '\n';
}

int main() {
    getline(fin, s);
    n = s.size();

    manacher();
    return 0;
}