Как оптимизировать алгоритм на python?

Question

def checking_for_substring(string_line, test_substring):
    substring=''.join(test_substring)
    if len(string_line)%len(substring)!=0:
        return False
    elif len(string_line)==len(substring):
        return True
    flag=0
    for index_string_line in range(0,len(string_line),len(substring)):  #index_limit() -> len(string_line)
        for index_substring in range(len(substring)):
            if string_line[index_string_line]==substring[index_substring]:
                index_string_line+=1
                flag+=1
        if flag==len(substring):
            flag=0
        else:
            return False
    return True

def main():
    string_line=str(input())
    test_substring=list()
    for i in range(len(string_line)):
        test_substring.append(string_line[i])
        if checking_for_substring(string_line, test_substring)==True:
            break
    print(int(len(string_line)/len(test_substring)))

if __name__=="__main__":
    main()

Как можно оптимизировать этот алгоритм, чтобы время работы была меньше 1 секунды.

ТЗ: Дана непустая строка S. Нужно найти такое наибольшее число k и строку T, что S совпадает со строкой T, выписанной k раз подряд.

Пример:
ввод: aaaaa
вывод: 5
ввод: abcabcabc
вывод: 3
ввод: abab
вывод: 2

Answer 1

Я бы действовал иначе. Ищем делители длины строки и проверяем строку для них.

В меру моего незнания Python получается вот такое (наверное, можно и лучше написать):

S = input()
for m in range(len(S),0,-1):
    k = len(S)//m
    if k*m != len(S):
        continue
    t = S[:k]
    p = ""
    for i in range(1,m+1):
        p = p + t
    if p == S:
        print(m)
        break

Answer 2

Решение за линейное время, использует z-функцию.
z[i] — это длина наибольшего общего префикса строки s и её i-го суффикса.
Если z[i]=n-i и n делится на i, то i является наименьшей длиной повторяемого сегмента.
Для приведенного примера z[4] = 8, т.е. s[4:]==s[:8], 8 совпадает с 12 - 4, длина сегмента 4, повторяется он три раза.

def z_function(s):
    n = len(s)
    z = [0]*n
    l = 0
    r = 0
    for i in range(1, n):
        if (i <= r):
            z[i] = min (r-i+1, z[i-l])
        while (i+z[i] < n) and (s[z[i]] == s[i+z[i]]):
            z[i] += 1
        if (i+z[i]-1 > r):
            l = i
            r = i+z[i]-1
    return z

s = 'abcdabcdabcd'
z = z_function(s)
n = len(s)
for i,x in enumerate(z):
    if i+x==n and n%i==0:
        print(n//i, s[:i])
        break

>>>   3  abcd

БЛОГ НА HUSL

Как оптимизировать алгоритм на python?

Ответы (2 шт):