การใช้งานแบบทั่วไปของอัลกอริทึม Longest Common Substring แบบ dynamic programming ใช้เวลา O(nm) โค้ดต่อไปนี้เป็นการใช้งานของอัลกอริทึม longest common substring:
ตัวอย่าง
def longest_common_substring(s1, s2):
m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
longest, x_longest = 0, 0
for x in range(1, 1 + len(s1)):
for y in range(1, 1 + len(s2)):
if s1[x - 1] == s2[y - 1]:
m[x][y] = m[x - 1][y - 1] + 1
if m[x][y] > longest:
longest = m[x][y]
x_longest = x
else:
m[x][y] = 0
return s1[x_longest - longest: x_longest]
print(longest_common_substring('wellbeing', 'welcome'))ผลลัพธ์
wel
วิธีการทำงาน:
- เริ่มต้นสร้างอาร์เรย์นับ (m) ทั้งหมดเป็น 0
- เริ่มจากแถวแรก เปรียบเทียบตัวอักษรแรกของ s1 กับทุกตัวอักษรใน s2
- ขณะวนลูปตัวอักษรใน s2 หากตรงกับตัวอักษรใน s1 ให้เพิ่มตัวนับ จะบันทึกที่ m[i][j] ซึ่งอยู่ตำแหน่งทแยงมุมล่างหนึ่งขั้น
ในที่สุดคืนสตริงย่อยที่ยาวที่สุดโดยใช้ดัชนีที่คำนวณในลูป
