# PBinfo #4672 – CountSeqMatch – Rezolvare C++

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

## Enunț

Se dau două șiruri de numere întregi a = a[1], a[2], ..., a[n] și b = b[1], b[2], ..., b[m], unde m < n. Spunem că o secvență a[i..i+m-1] = a[i], a[i+1], ..., a[i+m-1] se potrivește cu b dacă b conține, într-o ordine oarecare, toate numerele din secvența a[i..i+m-1]. De exemplu, dacă a = 3,5,1,2,2,5,3,8,1,2,3,5,2,1,1 și b = 2,2,1,5,3, atunci secvențele (3,5,1,2,2), (1,2,2,5,3), (1,2,3,5,2) și (2,3,5,2,1) se potrivesc cu b, pe când secvența 3,5,2,1,1 nu se potrivește cu b.

Cerința
Să se determine câte secvențe din a de lungime m se potrivesc cu b.

Date de intrare
Fișierul de intrare countseqmatch.in conține pe prima linie numărul n, pe a doua linie n numere naturale separate prin spații reprezentând elementele șirului a. Pe linia a treia se află numărul natural m, iar pe a patra linie se află cele m numere naturale reprezentând elementele șirului b.

Date de ieșire
Fișierul de ieșire countseqmatch.out va conține un singur număr natural reprezentând răspunsul la cerință.

Restricții și precizări

1 ≤ m < n ≤ 100.000
numerele din cele două șiruri sunt întregi cuprinse între -50.000 și 50.000

Exemplu:
countseqmatch.in

15
3 5 1 2 2 5 3 8 1 2 3 5 2 1 1
5
2 2 1 5 3
countseqmatch.out

4

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
ifstream fin("countseqmatch.in");
ofstream fout("countseqmatch.out");
int m, n, a[100003];
int fra[100003], frb[100003];
int main()
{
    int i, j, x, cnt = 0;
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> a[i];
        a[i] += 50000;
    }
    fin >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x;
        frb[x + 50000]++;
    }
    j = 1;
    for (i = 1; i <= n; i++)
    {
        x = a[i];
        fra[x]++;
        while (fra[x] > frb[x])
        {
            fra[a[j]]--;
            j++;
        }
        if (i - j + 1 == m) cnt++;
    }
    fout << cnt << "\n";
    fin.close();
    fout.close();
    return 0;
}
```

## Resurse

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