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

# 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)

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.