เมื่อจำเป็นต้องค้นหาสตริงย่อยทั่วไปที่ยาวที่สุดโดยใช้การเขียนโปรแกรมแบบไดนามิกด้วยวิธีการจากล่างขึ้นบน สามารถกำหนดวิธีการที่คำนวณวิธีแก้ปัญหาขนาดเล็กลงได้ ผลลัพธ์ของปัญหาเล็กๆ เหล่านี้ไม่จำเป็นต้องคำนวณซ้ำแล้วซ้ำอีก แต่สามารถเข้าถึงได้เมื่อจำเป็น ซึ่งจะนำไปสู่การพัฒนาแนวทางแก้ไขปัญหาที่ใหญ่กว่าในมือ
ด้านล่างนี้เป็นการสาธิตสำหรับสิ่งเดียวกัน -
ตัวอย่าง
def compute_lcw(string_1, string_2):
val = [[-1]*(len(string_2) + 1) for _ in range(len(string_1) + 1)]
for i in range(len(string_1) + 1):
val[i][len(string_2)] = 0
for j in range(len(string_2)):
val[len(string_1)][j] = 0
lcw_i = lcw_j = -1
lcw_len = 0
for i in range(len(string_1) - 1, -1, -1):
for j in range(len(string_2)):
if string_1[i] != string_2[j]:
val[i][j] = 0
else:
val[i][j] = 1 + val[i + 1][j + 1]
if lcw_len < val[i][j]:
lcw_len = val[i][j]
lcw_i = i
lcw_j = j
return lcw_len, lcw_i, lcw_j
string_1 = 'bull'
string_2 = 'bullied'
lcw_len, lcw_i, lcw_j = compute_lcw(string_1, string_2)
print("The longest common substring is : ")
if lcw_len > 0:
print(string_1[lcw_i:lcw_i + lcw_len]) ผลลัพธ์
The longest common substring is : bull
คำอธิบาย
- มีการกำหนดเมธอดชื่อ 'compute_lcw' ซึ่งรับสองสตริงเป็นพารามิเตอร์
- สตริงทั้งสองถูกวนซ้ำ และตรวจสอบเพื่อดูว่าพบสตริงที่ตรงกันในทั้งสองสตริงหรือไม่
- แม้เมื่อพบอักขระตัวเดียว อักขระนั้นก็ยังถูกเก็บไว้ในตัวแปรอื่น
- เมื่อสิ่งนี้ดำเนินต่อไปจนถึงจุดสิ้นสุดของสตริง สตริงอื่นจะเหมือนกับสตริงทั้งสองนี้
- มีการกำหนดสองสตริง และมีการเรียกเมธอดโดยการส่งผ่านสองสตริงนี้
- ข้อมูลการดำเนินการนี้ถูกกำหนดให้กับตัวแปร
- จากนั้นจะแสดงเป็นเอาต์พุตบนคอนโซล
