Chương trình tìm chuỗi con lặp lại k lần lớn nhất trong Python

Giả sử ta có chuỗi ký tự s. Chuỗi w gọi là k-repeating nếu w nối k lần là substring của s. Giá trị k-repeating lớn nhất của w là k lớn nhất thỏa mãn. Nếu w không phải substring của s, giá trị là 0. Cho s và w, tìm giá trị k-repeating lớn nhất.

Ví dụ: s = "papaya", w = "pa", kết quả 2 vì "pa" xuất hiện 2 lần trong "papaya".

Giải thuật

1. Count := s.count(w)
2. Nếu Count == 0: trả về 0
3. For i từ Count xuống 0:
   • Nếu w * i trong s: trả về i

Ví dụ (Python)

def solve(s, w):
    Count = s.count(w)
    if Count == 0:
        return 0
    for i in range(Count, 0, -1):
        if w * i in s:
            return i

s = "papaya"
w = "pa"
print(solve(s, w))

Input

"papaya", "pa"

Output

2