โปรแกรมนับจำนวน substring ที่ประกอบด้วย 1 เท่านั้นด้วย Python

สมมติว่าเรามีสตริงบाइनารี s เราต้องหาจำนวน substring ที่ตัวอักษรทุกตัวเป็น '1' คำตอบอาจใหญ่มาก จึงต้องคืนค่า modulo 10⁹ + 7

เช่น ถ้าข้อมูลเข้าเป็น s = "1011010" ผลลัพธ์จะเป็น 5 เพราะมี substring "1" จำนวน 4 ครั้ง และ "11" จำนวน 1 ครั้ง

ขั้นตอนการแก้ปัญหา

• กำหนด m = 10⁹ + 7
• กำหนด result = 0
• แบ่งสตริง b โดยแยกด้วยตัว '0' ได้รายการ div
• วนลูปแต่ละ x ใน div:
  • ถ้า x ว่าง ให้ข้าม
  • result += (len(x) × (len(x) + 1)) // 2 (สูตรจำนวน substring ในสตริงที่มีความยาว n)
• คืนค่า result mod m

ตัวอย่างโค้ด

def solve(s):
    m = 10**9 + 7
    result = 0
    for x in s.split('0'):
        if not x:
            continue
        result += (len(x) * (len(x) + 1)) // 2
    return result % m

s = "1011010"
print(solve(s))

ข้อมูลเข้า

"1011010"

ข้อมูลออก

5