0520 - Secventa2

Sursa: 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.

3

Rezolvare

Rezolvare ver. 1

# 0520 - Secventa2

def gaseste_secventa(x, y):
    n = len(x)
    m = len(y)
    cnt = 0
    for i in range(n-m+1):
        j = 0
        while j < m and x[i+j] == y[j]:
            j += 1
        if j == m:
            cnt += 1
    return cnt

if __name__ == "__main__":
    n = int(input())
    x = list(map(int, input().split()))
    m = int(input())
    y = list(map(int, input().split()))
    if n < m:
        print("Datele nu corespund restricțiilor impuse.")
    else:
        cnt = gaseste_secventa(x, y)
        print("Datele sunt introduse corect.")
        print(cnt)

Explicatie Rezolvare

Codul implementează o funcție find_sequence care primește două liste de numere și returnează numărul de apariții ale celui de-al doilea vector în primul vector. Funcția începe prin a verifica dacă lungimea celui de-al doilea vector este mai mare decât cel dintâi, caz în care returnează 0 deoarece vectorul căutat nu poate fi mai lung decât vectorul în care căutăm.

În continuare, se parcurge vectorul x cu o buclă for și se verifică pentru fiecare element al lui x dacă acesta este egal cu primul element din vectorul y. Dacă da, se verifică dacă o secvență de lungime m începe din acel punct în vectorul x. Dacă secvența este găsită, se crește contorul count cu 1.

La final, se returnează valoarea contorului count, care reprezintă numărul de apariții ale secvenței y în vectorul x.

Funcția main citește datele de intrare, verifică dacă acestea corespund restricțiilor impuse, și apoi apelează funcția find_sequence pentru a găsi numărul de apariții ale secvenței. În funcție de rezultatul returnat de aceasta, afișează mesajul corespunzător.