какова временная сложность моего кода генерации суффиксного массива - PullRequest
Новая
       29

какова временная сложность моего кода генерации суффиксного массива

0 голосов
/ 12 марта 2020

Я пытаюсь создать массив суффиксов, используя язык python. Моя программа не проходит все тесты и показывает ошибку тайм-аута. Я думаю, что его временная сложность составляет O (N logN logN). вот мой код: 

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)

Пожалуйста, предоставьте предложения, чтобы улучшить мой код и его временную сложность. Заранее спасибо

...