Chương trình kiểm tra mẫu độ dài m lặp lại k lần trong Python

Giả sử ta có mảng nums giá trị dương, tìm mẫu (pattern) độ dài m lặp lại k lần hoặc hơn. Mẫu là mảng con không chồng chéo (consecutive) lặp lại nhiều lần. Kiểm tra có tồn tại mẫu độ dài m lặp lại ≥ k lần hay không.

Ví dụ: nums = [3,5,1,4,3,1,4,3,1,4,3,9,6,1], m = 3, k = 2, kết quả True vì mẫu [1,4,3] xuất hiện 3 lần.

Giải thuật

1. For i từ 0 đến len(nums)-1:
   • sub1 := nums[i : i+m*k]
   • sub2 := nums[i : i+m] * k
   • Nếu sub1 == sub2: trả về True
2. Trả về False

Ví dụ (Python)

def solve(nums, m, k):
    for i in range(len(nums)):
        sub1 = nums[i:i+m*k]
        sub2 = nums[i:i+m] * k
        if sub1 == sub2:
            return True
    return False

nums = [3,5,1,4,3,1,4,3,1,4,3,9,6,1]
m = 3
k = 2
print(solve(nums, m, k))

Input

[3,5,1,4,3,1,4,3,1,4,3,9,6,1], 3, 2

Output

True