Cod sursa(job #2804004)

Utilizator DordeDorde Matei Dorde Data 20 noiembrie 2021 18:09:02
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;
int const N = 1e6 + 3;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
int p [2 * N];
char s [N] , x [2 * N];
int main()
{
    fin >> s;
    int n = strlen (s) , sz = 0;
    x [sz] = 'A';
    for(int i = 0 ; i < n ; ++ i){
        x [++ sz] = s [i];
        x [++ sz] = 'A';
    }
    n = sz + 1;
  //  cout << x << '\n';
    int l = 0 , r = -1;
    long long ans (0LL);
    for(int i = 0 ; i < n ; ++ i){
        int k (0);
        if (i > r)
            k = 0;
        else
            k = min (p [l + r - i] , r - i);
        while (i - k - 1 >= 0 && i + k + 1 < n && x [i - k - 1] == x [i + k + 1])
            ++ k;
        p [i] = k;
        if (i + k > r){
            l = i - k;
            r = i + k;
        }
     //   cout << p [i];
        if (p [i])
            ans += p [i] / 2;
    }
    fout << ans + strlen (s);
    return 0;
}