Улучшение временной сложности для нахождения LPS списка строк - PullRequest
Новая
       38

Улучшение временной сложности для нахождения LPS списка строк

0 голосов
/ 01 октября 2018

Я работал над проблемой, которая имеет следующее приглашение:

Вам дан массив A, состоящий из строк, состоящих только из букв «a» и «b».Каждая строка проходит ряд операций, где:

В момент 1 вы поворачиваете каждую строку по кругу на 1 букву. В момент 2 вы поворачиваете новые повернутые строки по кругу на 2 буквы. В момент 3 вы поворачиваете по кругу новые повернутые строки на 3 буквы. В момент i вы поворачиваете по кругу новые повернутые строки на буквы% длины (строки).

Через некоторое время строка становится равной своему первоначальному я.Как только строка становится равной себе, ее буквы снова начинают вращаться с первой буквы (процесс сбрасывается).Таким образом, если строке требуется t время, чтобы вернуться к оригиналу, в момент времени t + 1 одна буква будет повернута, и строка будет представлять собой исходное «я» в 2t раз.Вы должны найти минимальное время, когда максимальное количество строк равно их исходному я.Поскольку это время может быть очень большим, дайте ответ по модулю 109 + 7.

Примечание. Ваше решение будет работать на нескольких тестовых примерах, поэтому после их использования очищайте глобальные переменные.

Моя мысль былачтобы пройти по каждой строке, сгенерировать массив lps для проверки наличия подстроки, использовать тот факт, что позиция строки поворачивается на t (t + 1) / 2 при увеличении t, и проверить 1 из 2 случаев, чтобы определить, чтоминимальное т.Тем не менее, я сталкиваюсь с ошибкой превышения лимита времени для больших наборов строк.

Я ищу совет о том, как настроить мою программу, чтобы уменьшить сложность времени. 

def gcd(A,B):
    if B> A:
        A,B = B,A
    while B!=0:
        temp = B
        B=A%B
        A=temp
    return A


def solve(A):
    times = []
    for i in range (0, len(A)):
        j=1
        m=len(A[i])
        lps = [0]*m
        p=0
        for k in range(1,m):     #generate LPS of KMP to find longest subsequence
            while p > 0 and A[i][k] != A[p]:
                p = lps[p-1]
            if A[i][k]==A[i][p]:
                p+=1
            lps[i]=j
        if lps[-1] > 0:
            while ((j*(j+1))//2)%lps[-1] != 0:
                j+=1
            times.append(j)
        else: 
            while ((j*(j+1))//2)%len(A[i]) != 0:
                j+=1
            times.append(j)
    lcm = times[0]
    for i in times[1:]:
        lcm = lcm*i/gcd(lcm, i)
    lcm = int(lcm%((1e9)+7))
    return lcm

###testing below this point
A=["a", "ababa", "aba"]
print(solve(A))

Итерациячерез каждый список - O (n), где n - количество списков
У меня сложилось впечатление, что создание списка lps было O (n + m)
И затем далее циклы while для определения t вложены один раз, поэтому общая сложность времени должна быть O (n * k), где k = 2 * средняя длина списка -1 (или максимальное значение t).

Я хотел бы знать любые предложения, как улучшить сложность времени,или код в целом.

...