Cod sursa(job #2586404)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 20 martie 2020 20:19:44
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
#define DIM 2000010
using namespace std;

ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
char s[DIM],v[DIM];
int p[DIM];
int n,m,i;
int manacher (){
    m = strlen (s+1), n = 0;
    v[++n] = '*';
    for (i=1;i<=m;i++){
        v[++n] = s[i];
        v[++n] = '*';
    }
    /// p[i] - cu cat se poate extinde un palindrom cu centrul in i
    int c = 0, Left = 0, Right = 0;
    long long sol = 0;
    for (i=1;i<=n;i++){

        if (i > Right){
            /// extind cat pot de la i
            p[i] = 1;
            Left = Right = c = i;
            while (Left > 1 && Right < n && v[Left-1] == v[Right+1]){
                p[i]++;
                Left--, Right++;
            }
        } else {

            int mirror = c - (i - c);

            p[i] = min (p[mirror], Right - i + 1);

            /// acum incercam sa extindem
            int st = i - p[i];
            int dr = i + p[i];
            while (st >= 1 && dr <= n && v[st] == v[dr]){
                p[i]++;
                st--, dr++;
            }

            if (i + p[i] - 1 > Right){
                c = i;
                Left = i - p[i] + 1;
                Right = i + p[i] - 1;
            }
        }

        //maxi = max (maxi,p[i]);
        sol += p[i] / 2;
    }

    return sol;

}
int main (){

    fin>>s+1;
    fout<<manacher();

  //  for (i=1;i<=n;i++)
    //    fout<<p[i]<<" ";


    return 0;
}