0519 - Secventa1

Sursa: 0519 - Secventa1

---

Cerinţa

Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se verifice dacă vectorul y este 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 p, reprezentând poziția din vectorul x de unde începe secvența y, dacă y este secvență în x, respectiv mesajul NU dacă y nu este secvență în x, 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
• elementele celor doi vectori vor fi indexate de la 1
• dacă vectorul y este de mai multe ori secvență în x se va afișa poziția de început a primei apariții

Exemplu 1

Intrare

10

8 5 8 5 2 3 10 7 1 6

6

8 5 2 3 10 7

Ieșire

Datele sunt introduse corect.

3

Exemplu 2

Intrare

1

2 3 4 5 6 7 8 3 1 11 2

4

1 2 3 4 5 6

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0519 - Secventa1

def find_sequence(x, y):

   n = len(x)
   m = len(y)
   if m > n:
       return -1
   for i in range(n - m + 1):
       if x[i:i+m] == y:
           return i + 1
   return -1

def validate_input(n, m):

   if not(1 <= m <= n <= 1000):
       return False
   return True

if __name__ == '__main__':

   # Citim input-ul
   n = int(input())
   x = list(map(int, input().split()))
   m = int(input())
   y = list(map(int, input().split()))

   # Validam input-ul
   if not validate_input(n, m):
       print('Datele nu corespund restrictiilor impuse.')
       exit()

   # Gasim secventa si afisam raspunsul
   poz = find_sequence(x, y)
   if poz != -1:
       print('Datele sunt introduse corect.')
       print(poz)
   else:
       print('Datele sunt introduse corect.')
       print('NU')

</syntaxhighlight>

Explicatie Rezolvare

Funcția validate_input verifică restricțiile impuse și returnează True dacă datele sunt valide, sau False în caz contrar.

Funcția find_subsequence caută secvența y în vectorul x și returnează poziția de început a secvenței sau -1 dacă secvența nu a fost găsită.

În funcția main citim datele de intrare și le trimitem la funcția de validare. Dacă datele sunt valide, afișăm mesajul "Datele sunt introduse corect." și apoi apelăm funcția de rezolvare pentru a găsi poziția de început a secvenței y în vectorul x. În caz contrar, afișăm mesajul "Datele nu corespund restricțiilor impuse."