Cod sursa(job #3195462)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 20 ianuarie 2024 21:34:19
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>

using namespace std;
using ll = long long;
const int NMAX = 2000012;

ifstream cin("pscpld.in");
ofstream cout("pscpld.out");

int v[NMAX];
int main()
{
    string a, s;
    cin >> a;
    s += '&';
    s += '*';
    for(int i = 0; i < a.size(); i++) {
        s += a[i];
        s += '*';
    }
    s += '#';
    int imp = 0, end = 0;
    for(int i = 0; i < s.size(); i++) {
        if(i < end && v[2 * imp - i] < end - i)
            v[i] = v[2 * imp - i];
        else {
            v[i] = max(0, end - i);
            while(i + v[i] + 1 < s.size() && i - v[i] - 1 >= 0 &&  s[i + v[i] + 1] == s[i - v[i] - 1])
                v[i]++;
            imp = i;
            end = i + v[i];
        }
    }
    ll ans = 0;
    for(int i = 0; i < s.size(); i++)
        ans += (v[i] + 1) / 2;
    cout << ans;


    /*for(int i = 0; i < s.size(); i++)
        cout << s[i] << " ";
    cout << '\n';
    for(int i = 0; i < s.size(); i++)
        cout << v[i] << " ";*/
    return 0;
}