Rezolvare PBinfo #4672

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