โปรแกรมหา Maximum k-Repeating Substring ใน Python

โจทย์

มี Sequence s และ String w หา k สูงสุดที่ w ซ้ำ k ติดกันเป็น Substring ของ s (k-Repeating) ถ้าไม่มีคืน 0

ตัวอย่าง: s="papaya", w="pa" → Output: 2 ("papa" อยู่ใน "papaya")

อัลกอริธึม

1. นับจำนวน w ใน s แบบ Overlap ได้ (Upper Bound)
2. ลอง k จากมากไปน้อย: ถ้า w*k ใน s → คืน k

โค้ด 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))  # Output: 2

Input / Output

Input:  "papaya", "pa"
Output: 2