vic57Весьма неплохо. Я только вот недавно додумался использовать индексы(функцию find)
И всё же, мне кажется, должен быть способ, просто в одном регулярном выражении это отыскать… или мне кажется
vic57Весьма неплохо. Я только вот недавно додумался использовать индексы(функцию find)
oldjaponec@gmail.comТебе кажется. В регулярных выражениях ничего сложного нет. Их вполне реально выучить, имея только школьную базу навыков. Просто существуют задачи, которые непригодны для решения регулярными выражениями. Нельзя считать так: если в строке надо что-то найти, то для этого подойдут регулярные выражения. Это далеко не всегда так. Теоретически они подходят ко многому, а на практике очень часто получается неподходящий результат и нарушается принцип ясности кода.
И всё же, мне кажется, должен быть способ, просто в одном регулярном выражении это отыскать… или мне кажется
oldjaponec@gmail.comмой метод повторяет ф-цию strstr() из Си, проще вряд ли прлучится. в регах под капотом те же циклы
И всё же, мне кажется, должен быть способ, просто в одном регулярном выражении это отыскать… или мне кажется
s = 'arefhjaref!!' out = [] for i in range(len(s)): t = s[i:] for j in range(2,len(t)): s1,s2 = t[:j],t[j:] if s2.find(s1) < 0: continue out.append(s1) out.sort(key = lambda x: len(x),reverse=True) print(out)
s = 'arefhjjjjaref!!' out = [] for i in range(len(s)): t = s[i:] for j in range(2,len(t)): s1,s2 = t[:j],t[j:] if s2.find(s1) < 0: continue out.append(s1) out.sort(key = lambda x: len(x),reverse=True) print(out)
>>>['aref', 'are', 'ref', 'ar', 're', 'ef', 'jj']
vic57ну и здесь вы не правы. Задача решается в один проход. Посмотрите на мой пример выше, там как раз реализовано решение в один проход. У вас вложенные циклы, что сразу значительно увеличит вычислительную сложность. Я сделал небольшой тест:
проще вряд ли прлучится
from itertools import takewhile import random import timeit def find_longest_substr1(string): longest_seq = "" s = string while s: char = s[0] seq = list(takewhile(lambda i: i == char, s)) length = len(seq) if length > len(longest_seq): longest_seq = seq s = s[length:] return "".join(longest_seq) def find_longest_substr2(string): out = [] for i in range(len(string)): t = string[i:] for j in range(2, len(t)): s1,s2 = t[:j], t[j:] if s2.find(s1) < 0: continue out.append(s1) out.sort(key=lambda x: len(x), reverse=True) return out _s = ["a", "b", "c", "d", "e"] s = "".join(random.choice(_s) for _ in range(1000)) print(timeit.timeit("find_longest_substr1(s)", setup="from __main__ import find_longest_substr1, s", number=1)) print(timeit.timeit("find_longest_substr2(s)", setup="from __main__ import find_longest_substr2, s", number=1))
>>>0.0018036999999999984
>>>0.5519485999999999
import timeit def test(): from itertools import takewhile print(timeit.timeit("test", setup="from __main__ import test", number=1))
3.9211334579292156e-07
FishHookпервый элемент в out
вы, вероятно чего-то не додумали, в выводу вашей программы я не вижу самой длинной подстроки
FishHookпитоновские циклы медленные. если б мне надо было - сделал бы Си - модуль
на строке из тысячи символов ваш код медленнее в 550 раз