סמסטר א' מועד א' 2013
Uri (guest) 06 Feb 2015 13:19
שלום לכולם,
בשאלה 5 סעיף א' של המבחן המדובר שבכותרת יש דרישה לסיבוכיות זמן ריצה של
O(mnk)
אני הצלחתי לכתוב לפי הרעיון של קארפ-רבין אלגוריתם בזמן ריצה
O(m^2n^2)
אשמח אם מישהו יוכל לתת לי הכוונה לאיך לשפר זאת
תודה.
def fp(lst,base=2**16,r=2**32 - 3):
f = lst[0]
for i in range(1,len(lst)):
f = (f*base+lst[i])
return f
def max_repetition1(lst1,lst2):
dic = dict()
M = max(len(lst1),len(lst2))
base = 2**16
matches = []
for k1 in range(2,len(lst1)+1):
b_power = pow(2**16,k1-1)
fp1 = fp(lst1[0:k1])
## print("list:",lst1[0:k1],"fingerprint:",fp1)
dic[fp1] = lst1[0:k1]
for n1 in range(1,len(lst1)-k1+1):
fp1 = fp(lst1[n1:n1+k1]) #((fp1-lst1[n1]*b_power)*base) + lst1[n1+k1]
## print("list:",lst1[n1:n1+k1],"fingerprint:",fp1)
if dic.get(fp1) == None:
dic[fp1] = [lst1[n1:n1+k1]]
for k2 in range(2,len(lst2)+1):
b_power = pow(2**16,k2-1)
fp2 = fp(lst2[0:k2])
## print("list:",lst2[0:k2],"fingerprint:",fp2)
if dic.get(fp2) != None:
matches += [lst2[0:k2]]
else:
dic[fp2] = [lst2[0:k2]]
for n2 in range(1,len(lst2)-k2+1):
fp2 = fp(lst2[n2:n2+k2])#((fp2-lst2[n2]*b_power)*base) + lst2[n2+k2]
## print("list:",lst2[n2:n2+k2],"fingerprint:",fp2)
if dic.get(fp2) != None:
matches += [lst2[n2:n2+k2]]
else:
dic[fp2] = [lst2[n2:n2+k2]]
if len(matches)>0:
return len(matches[-1])
else:
return Noneבנוסף בשאלה 4 של אותו מבחן ברורה לי התשובה אבל לא הצלחתי למצוא דוגמא לכך יוצא לי תמיד שמספר הקריאות לNext הוא שווה או קטן למקרה המקורי.
תודה ובהצלחה לכולנו :)
