В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

pro.algorithms

1753 membersпожаловаться на группу
2020 May 26

 P

 ‌‌Gleb Pilipets... in pro.algorithms
Ребят, а раз зашла речь об автоматах, то у меня вопрос о конечном автомате.

Как на автомате распарсить, например такое регулярное выражение '[A-Za-z0-9]+'
То есть здесь же очень много переходов будет, разве нет?
источник
01:53пожаловаться#1

MB

Mikail Bagishov in pro.algorithms
 ‌‌Gleb Pilipets
Ребят, а раз зашла речь об автоматах, то у меня вопрос о конечном автомате.

Как на автомате распарсить, например такое регулярное выражение '[A-Za-z0-9]+'
То есть здесь же очень много переходов будет, разве нет?
Переходов будет примерно 62
источник
01:53пожаловаться#2

 P

 ‌‌Gleb Pilipets... in pro.algorithms
++
источник
01:53пожаловаться#3

 P

 ‌‌Gleb Pilipets... in pro.algorithms
Это не много?
источник
01:54пожаловаться#4

MB

Mikail Bagishov in pro.algorithms
Это O(N * Sigma)
источник
01:54пожаловаться#5

I

Ioann_V in pro.algorithms
Mikail Bagishov
Это O(N * Sigma)
Хммм... а мою задачу, можно ли решить за ту же ассимптотику, при условии, что нам надо понять, сколько раз подстроки в позиции i строки S, встречаются в той же позиции, в других строках?
источник
02:06пожаловаться#6

I

Ioann_V in pro.algorithms
Я про линию.
источник
02:06пожаловаться#7

М

Манкурт Кобейн... in pro.algorithms
Mikail Bagishov
А разве не чистая линия?
Смотря как напишешь. Вообще, можно за линию
источник
02:23пожаловаться#8

I

Ioann_V in pro.algorithms
Ioann_V
Хммм... а мою задачу, можно ли решить за ту же ассимптотику, при условии, что нам надо понять, сколько раз подстроки в позиции i строки S, встречаются в той же позиции, в других строках?
Придумал. Можно же позицию суффикса как первый символ этого суффикса брать.
источник
02:38пожаловаться#9

CD

Constantine Drozdov in pro.algorithms
Ioann_V
То есть, можно свести задачу к:
Дана строка, сколько раз в ней встречаются разные её подстроки.
на суфмассиве такое должно быть просто лучше
источник
04:21пожаловаться#10

CD

Constantine Drozdov in pro.algorithms
суфмассив не жрет безумную константу памяти
источник
04:21пожаловаться#11

I

Ioann_V in pro.algorithms
Ioann_V
Хммм... а мою задачу, можно ли решить за ту же ассимптотику, при условии, что нам надо понять, сколько раз подстроки в позиции i строки S, встречаются в той же позиции, в других строках?
А если так?
источник
04:22пожаловаться#12

I

Ioann_V in pro.algorithms
У меня идея, добавить перед каждым символом, его индекс
источник
04:22пожаловаться#13

CD

Constantine Drozdov in pro.algorithms
мне не очень понятно про "подстроки в позиции"
источник
04:22пожаловаться#14

I

Ioann_V in pro.algorithms
он нигде не встречается в строке
источник
04:22пожаловаться#15

CD

Constantine Drozdov in pro.algorithms
но ты про любую подстроку исходной можешь понять, сколько оно там встречается
источник
04:22пожаловаться#16

I

Ioann_V in pro.algorithms
Constantine Drozdov
мне не очень понятно про "подстроки в позиции"
Ну вот есть у тебя строка
абц
и строк
бца
и строка
кбц
источник
04:23пожаловаться#17

I

Ioann_V in pro.algorithms
так вот в первой и второй в позиции 1(отсчет с нуля)
источник
04:23пожаловаться#18

CD

Constantine Drozdov in pro.algorithms
у тебя просто вся структура подстрок есть
источник
04:23пожаловаться#19

I

Ioann_V in pro.algorithms
бц и в третьей бц
источник
04:23пожаловаться#20