我正在尝试使用python语言创建后缀数组。我的程序没有通过所有测试用例,并且显示超时错误。我认为它的时间复杂度是O(NlogNlogN)。 这是我的密码:
def criteria1(s):
return s[0]
def criteria2(s):
return s[1]
def criteria3(s):
return s[0][0]
text='banana'
l=len(text)
s=[]
for i in range(l):
s.append([[ord(text[i])-ord('a'),None],i]) # s is list of [[rank1,rank2],original_index] where rank1 is set according to first character of suffices of 'text'
doTill=1
while doTill<l:
for i in range(l): # assigning the second rank
try:
s[i][0][1]=s[i+doTill][0][0]
except IndexError:
s[i][0][1]=-1
s.sort(key=criteria1) # sorting based on [rank1,rank2]
#print('first sort',s)
temp=list(s[0][0]) # now assigning new rank1 based on [rank1,rank2]
s[0][0][0]=0 # setting rank1 of first element to 0
r=0
for i in range(1,l):
if temp==s[i][0]:
s[i][0][0]=r
else:
temp=list(s[i][0])
r+=1
s[i][0][0]=r
#print('reassign ranks',s)
s.sort(key=criteria2) # again sorting based on original_index of suffices
doTill*=2
s.sort(key=criteria3) # now getting the required suffix array from s by first sorting it according to rank1 and then getting original_indices
for i in range(l):
s[i]=s[i][1]
print(s)
请提供改进我的代码及其时间复杂性的建议。 提前谢谢
目前没有回答
相关问题 更多 >
编程相关推荐