Editing 0520 - Secventa2

Sursa: [https://www.pbinfo.ro/probleme/520/secventa2 0520 - Secventa2]
----
== Cerinţa ==
Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se determine de câte ori este vectorul y secvență în vectorul x.
== Date de intrare ==
Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y.
== Date de ieșire == 
Dacă datele sunt introduse corect, pe ecran se va afișa: 
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''va afișa pe ecran numărul C, reprezentând valoarea cerută''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
== Restricţii şi precizări ==
* 1 ≤ m ≤ n ≤ 1000
== Exemplu 1 ==
; Intrare
: 10
: 8 5 8 5 8 3 8 5 8 6 
: 3
: 8 5 8
; Ieșire
: Datele sunt introduse corect.
: 3

== Exemplu 2 ==
; Intrare
: 11
: 2 3 4 5 7 1 8 3 2
: 2 
: 1 2 1 
; Ieșire
: Datele nu corespund restricțiilor impuse.

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 0520 - Secventa2

import sys

def validate_input(n, x, m, y):
    if not(1 <= n <= 1000) or not(1 <= m <= 1000):
        return False
    if len(x) != n or len(y) != m:
        return False
    for elem in x + y:
        if not isinstance(elem, int) or elem < 0:
            return False
    return True


def count_subsequences(n, x, m, y):
    count = 0

    for i in range(n-m+1):
        # Verificăm dacă vectorul y apare ca secvență în x începând de la poziția i
        if x[i:i+m] == y:
            count += 1
    
    return count


if __name__ == "__main__":
    # Citim datele de intrare
    n = int(input())
    x = list(map(int, input().split()))
    m = int(input())
    y = list(map(int, input().split()))
    
    # Validăm datele de intrare
    if not validate_input(n, x, m, y):
        print("Datele nu corespund restricțiilor impuse.")
        sys.exit(0)

    # Datele sunt introduse corect
    print("Datele sunt introduse corect.")
    
    # Calculăm și afișăm numărul de apariții ale lui y ca secvență în x
    print(count_subsequences(n, x, m, y))


</syntaxhighlight>
== Explicatie Rezolvare ==

validate_input(n, x, m, y) - această funcție primește ca argumente numărul de elemente ale vectorului x (n), vectorul x, numărul de elemente ale vectorului y (m) și vectorul y. Funcția verifică dacă datele de intrare sunt valide, adică dacă 1 <= n <= 1000, 1 <= m <= 1000, vectorii x și y au lungimea corespunzătoare numărului de elemente specificat, iar toate elementele din x și y sunt numere întregi pozitive. Funcția returnează True dacă datele de intrare sunt valide și False în caz contrar.

count_subsequences(n, x, m, y) - această funcție primește ca argumente numărul de elemente ale vectorului x (n), vectorul x, numărul de elemente ale vectorului y (m) și vectorul y. Funcția parcurge toate pozițiile posibile din vectorul x și verifică dacă vectorul y apare ca subsecvență în x începând de la fiecare poziție. Pentru a face aceasta, se verifică egalitatea între slice-urile de lungime m din x și vectorul y. Dacă x[i:i+m] == y, numărul de apariții al vectorului y ca subsecvență în x este incrementat cu 1. La final, funcția returnează numărul de apariții al vectorului y ca subsecvență în x.

În blocul principal if __name__ == "__main__", datele de intrare sunt citite de la tastatură și apoi verificate prin apelul funcției validate_input. Dacă datele sunt valide, se afișează mesajul "Datele sunt introduse corect." și numărul de apariții al vectorului y ca subsecvență în x. În caz contrar, se afișează mesajul "Datele nu corespund restricțiilor impuse.".