Cod sursa(job #3367897)

Utilizator JenJenCristache Ion JenJen Data 11 octombrie 2026 21:05:29
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <string.h>
#include <cmath>
using namespace std;

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

string sir;
char temp[2000005];
int pal[2000005];
int n;
long long ans;

void solve()
{
    int poz = 0;
    temp[poz++] = '#';
    for (int i = 0; i < n; i++)
    {
        temp[poz++] = sir[i];
        temp[poz++] = '#';
    }

    int st = 0;
    int dr = -1;

    int k = 0;
    for (int i = 0; i < poz; i++)
    {
        if (i > dr) k = 1;
        else k = min(pal[dr + st - i], dr - i + 1);

        while (i - k >= 0 && i + k < poz && temp[i - k] == temp[i + k])
        {
            k++;
        }

        pal[i] = k--;
        ans += pal[i] / 2LL;

        if (i + k > dr)
        {
            dr = i + k;
            st = i - k;
        }
    }
}
int main()
{
    cin >> sir;

    n = sir.size();
    solve();

    cout << ans;

}