# PBinfo #3492 – PalPal – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se dă un șir s care conține litere mici ale alfabetului englez, urmat de un număr natural k. Să se afișeze câte subsecvențe ale șirului s de lungime 1, 2, … k sunt palindromuri.

Date de intrare
Fișierul de intrare palpal.in conține pe prima linie un șir s și pe următoarea linie un număr natural k.

Date de ieșire
Fișierul de ieșire palpal.out va conține k linii. Pe linia i (1 ≤ i ≤ k) se va găsi numărul de subsecvențe de i caractere care sunt palindromuri.

Restricții și precizări

1 ≤ k ≤ 1000
șirul s are maxim 20000 de caractere
Prin subsecvență a unui șir de caractere se înțelege o succesiune de unul sau mai multe caractere din șir aflate pe poziții consecutive.
Un șir de caractere este palindrom dacă se citește la fel de la stânga la dreapta și de la dreapta la stânga.

Exemplu:
palpal.in

eaaebeadaebcc
5
palpal.out

13
2
2
1
2
Explicație
Subsecvențe palindrom de lungime 1: e, a, a, e, b, e, a, d, a, e, b, c, c.
Subsecvențe palindrom de lungime 2: aa, cc.
Subsecvențe palindrom de lungime 3: ebe, ada.
Subsecvențe palindrom de lungime 4: eaae.
Subsecvențe palindrom de lungime 5: aebea, eadae.

## Cod sursă C++

```cpp
#include <fstream>
#define NM 1000002
#include <set>
#include <cstring>
using namespace std;
ifstream f("palpal.in");
ofstream g("palpal.out");
int n,element,i,j,k,tip;
char s[NM];
set < int > par,impar;
int main()
{
    f.get(s,NM);
    n=strlen(s);
    for(i=0; i<n; i++)
    {
        impar.insert(i);
        if(i<n-1&&s[i]==s[i+1])
            par.insert(i);
    }
    f>>k;
    for(j=1; j<=k; j++)
    {
        if(impar.size()==0&&par.size()==0)
        {
            g<<0<<'\n';
            continue;
        }
        if(j==1) g<<n<<'\n';
        else if(j==2) g<<par.size()<<'\n';
        else
        {
            if(j%2==1)
            {
                for(auto it=impar.begin(); it!=impar.end();)
                {
                    if((*it-(j/2)<0)||(*it+(j/2)>=n))
                        it=impar.erase(it);
                    else if(s[*it-(j/2)]!=s[*it+(j/2)])
                        it=impar.erase(it);
                    else
                        it++;
                }
                g<<impar.size()<<'\n';
            }
            else
            {
                for(auto it=par.begin(); it!=par.end();)
                {
                    if((*it-((j-2)/2)<0)||(*it+(j/2))>=n)
                        it=par.erase(it);
                    else if(s[*it-(j-2)/2]!=s[*it+(j/2)])
                        it=par.erase(it);
                    else
                        it++;
                }
                g<<par.size()<<'\n';
            }
        }
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3492)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3492/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3492/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)