Форум сайта python.su
Помогите разобраться с регулярными выражениями. Я новичок, но, вроде, не такой глупый. Уже десяток раз перечитал документацию по синтаксису, а, как не получал от них то, что нужно, так и не получаю. У меня уже крыша едет от того, как это работает на практике.
Задача такая. Дана строка. Надо определить самую длинную повторяющуюся подстроку.
Пример:
'aaaa' == ‘aa’
'aghtfghkofgh' == ‘fgh’
'abc' == None
Вот это здесь не работает:
((.+)+)((.)*)\1+
(?= (\w+)(.*))\1+
(?= (\w+)+)((.*))\1{2,}
((\w+)+)(.*)\1{2}
(.+)(?:.*\1){2,}
(?:(.*)*)((\w+)+)(?:(.*)*){2,}
Отредактировано oldjaponec@gmail.com (Сен. 12, 2019 01:07:08)
Офлайн
oldjaponec@gmail.comЗадание именно в регулярных выражениях? Именно через них надо сделать?
Задача такая. Дана строка. Надо определить самую длинную повторяющуюся подстроку.
Пример:
Офлайн
py.user.nextНу, как бы нет. Просто тут уже принципиально, возможно ли вообще это решить с помощью регулярных выражений. Хотелось бы в них разобраться на примере этого задания. Кроме того, лично у меня, другие пути решения слишком большой перебор предполагают. Загвоздка, кстати, не малая, ещё в том, что повторяющиеся подстроки не должны перекрывать друг друга
Офлайн
Ну, это как с задачей по распознаванию всех возможных E-mail-адресов через регекспы - сделать-то можно, только на выходе получается ужос. В то же время правила питона предполагают ясность кода, чтобы избегать закрадывания багов в нём.
Эту задачу не надо делать через регекспы. Лёгкий конечный автомат спасёт отца русской демократии.
wiki. конечный автомат
wiki. конечный автомат. пример
Офлайн
oldjaponec@gmail.comНадо определить самую длинную повторяющуюся миним 2 раза подстроку те подстрока как максимум в половину длины строки
Надо определить самую длинную повторяющуюся подстроку.
Отредактировано AD0DE412 (Сен. 12, 2019 22:41:36)
Офлайн
py.user.next
Спасибо. Посмотрю. В любом случае, это точно лишним не будет
Офлайн
AD0DE412Да, именно так. Кстати, в этом ключе я не думал. Спасибо за идею
Офлайн
Короче, программа такая решала эту задачу быстро и качественно, пока ей не попалась строка ‘arefhjaref!!’, результат которой почему-то ‘!’, а не ‘aref’
l='arefhjaref!!'
k,i=len(l)//2,0
if l!='':
while k>0:
if i==k:k-=1;i==0
if l.count(l[i:k+i])>1:print(l[i:k+i])
i+=1
Отредактировано oldjaponec@gmail.com (Сен. 13, 2019 03:39:39)
Офлайн
ваш вариант не выбирает всех возможных случеев
мне кажется что нужно набирать базу всех сочетаний последовотельностей символов не превышающих половину длины строки после чего прогнать на вхождение в строку этих последовательностей
какая самая длинная и которая повторяется и не пересекается та и есть наша подстрока (ответов может быть от нет до несколко)
зы думаю как это будет в коде
ззы возможно что то из итертулз
Отредактировано AD0DE412 (Сен. 13, 2019 08:37:38)
Офлайн
import re s = 'arefhjaref!!' out = [] for i in range(len(s)//2): tmp = re.findall(r'(.+).*?\1', s[i:])[0] if s.count(tmp) > 1 and len(tmp) > 1: out.append(tmp) out.sort(key=lambda x: len(x)) print(out)
Офлайн