Cod sursa(job #2870699)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 12 martie 2022 15:10:59
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <iostream>
#include <string>
using namespace std;

ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");

string buff, a;
int pal[2000001];

int main()
{
    int n, i, l, st, dr;
    long long rasp;

    fin >> buff;
    a += '#';
    for (i = 0; i<buff.size(); i++)
    {
        a += buff[i];
        a += '#';
    }
    n = a.size();

    st = dr = -1;
    for (i = 0; i<n; i++)
    {
        if (i <= dr)
            l = min (pal[st+dr-i], dr-i+1);
        else
            l = 1;

        while (0 <= i-l && i+l < n && a[i-l] == a[i+l])
            l++;

        pal[i] = l;
        if (i+l-1 > dr)
        {
            dr = i+l-1;
            st = i-l+1;
        }
    }

    rasp = 0;
    for (i = 0; i<n; i++)
        rasp = rasp + pal[i]/2;
    fout << rasp;
    return 0;
}