สามารถใช้ defaultdict นับแต่ละสตริงย่อยที่เริ่มต้นที่แต่ละตำแหน่งในสตริงอินพุต เมธอด getsubs เป็น generator ที่คืนสตริงย่อยที่สั้นลงทุกครั้งที่เรียก
ตัวอย่าง
from collections import defaultdict
def getsubs(loc, s):
substr = s[loc:]
i = -1
while substr:
yield substr
substr = s[loc:i]
i -= 1
def longestRepetitiveSubstring(r):
occ = defaultdict(int)
# นับการเกิดของทุกสตริงย่อย
for i in range(len(r)):
for sub in getsubs(i, r):
occ[sub] += 1
# กรองสตริงย่อยที่เกิดน้อยกว่า 2 ครั้ง
filtered = [k for k, v in occ.items() if v >= 2]
if filtered:
maxkey = max(filtered, key=len) # หาสตริงยาวที่สุด
return maxkey
else:
raise ValueError("no repetitions of any substring of '%s' with 2 or more occurrences" % (r))
longestRepetitiveSubstring("hellopeople18654randomtexthellopeoplefromallaroundthe world")ผลลัพธ์
จะได้ผลลัพธ์:
'hellopeople'
