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

Programul 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.

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

Intrare

10

8 5 8 5 2 3 10 7 1 6

6

8 5 2 3 10 7

Ieșire

3

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0519 - Secventa1

def read_input():

   n = int(input())
   x = list(map(int, input().split()))
   m = int(input())
   y = list(map(int, input().split()))
   return n, x, m, y

def is_subsequence(n, x, m, y):

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

def validate_output(result):

   print(result) if result != -1 else print("NU")

if __name__ == "__main__":

   n, x, m, y = read_input()
   result = is_subsequence(n, x, m, y)
   validate_output(result)

</syntaxhighlight>

Explicatie Rezolvare

Funcția read_input citește datele de intrare de la tastatură și returnează valorile citite sub formă de tuple.

Funcția is_subsequence primește cele patru variabile și parcurge vectorul x cu o fereastră de lungime m. Dacă fereastra curentă este identică cu vectorul y, atunci întoarce poziția de început a secvenței (i + 1). Dacă nu găsește nicio secvență, întoarce -1.

Funcția validate_output primește rezultatul întors de is_subsequence și afișează poziția găsită sau mesajul "NU" în caz contrar.

În blocul if __name__ == "__main__":, apelăm funcțiile în ordinea potrivită pentru a rezolva problema.