БВ
reduction, expansion и т.д.?
Pow, log например)
Size: a a a
2020 August 27
N
Как сделать простейшую проверку на соответствию выражению , которое допускает использование . (Точки) и *(звёздочки). Т.е могут быть регулярки вида "c*" , "c..." , "c*v."
GK
Ну можно написать динамику dp[i][j] можно ли первыми i символами регулярки покрыть j символов выражения
С
Nikolay
Как сделать простейшую проверку на соответствию выражению , которое допускает использование . (Точки) и *(звёздочки). Т.е могут быть регулярки вида "c*" , "c..." , "c*v."
то есть? есть некий шаблон - например "world" и есть некое выражение, например "w*r.d" - как определить, что выражение соответствует шаблону? простой цикл чем не устраивает?
size_t i =0; while(i<size){ if(t[i]==w[i] || t[i]=='.'||t[i]=='*') i++;else break; return i==size; ?N
Сергей
то есть? есть некий шаблон - например "world" и есть некое выражение, например "w*r.d" - как определить, что выражение соответствует шаблону? простой цикл чем не устраивает?
size_t i =0; while(i<size){ if(t[i]==w[i] || t[i]=='.'||t[i]=='*') i++;else break; return i==size; ?* - это значит предыдущий встреча ется 0 или более раз. У вас вроде это просто любой символ
С
Nikolay
* - это значит предыдущий встреча ется 0 или более раз. У вас вроде это просто любой символ
в вопросе, который был задан - об этом ни слова не сказано. или я (что более вероятно) его вообще не понял.
EZ
Nikolay
Как сделать простейшую проверку на соответствию выражению , которое допускает использование . (Точки) и *(звёздочки). Т.е могут быть регулярки вида "c*" , "c..." , "c*v."
написать автомат?)
2020 August 28
V
есть строка S длиной N<2*10^4, и есть код, который делает S[:min(200, N)].find("константная строка")
какая сложность? O(N) или O(1)?
какая сложность? O(N) или O(1)?
EZ
есть строка S длиной N<2*10^4, и есть код, который делает S[:min(200, N)].find("константная строка")
какая сложность? O(N) или O(1)?
какая сложность? O(N) или O(1)?
если N ограничен то O(N)=O(1)
EZ
но тут O(1) энивей
ПК
ну хз, нужно почитать доку питона
EZ
ну хз, нужно почитать доку питона
я предположил что это псевдокод
ПК
А, ну тогда — да
V
ну хз, нужно почитать доку питона
ну предположим что s1.find(s2) выполняется за len(s1)*len(s2)
V
я предположил что это псевдокод
да, это скорее псевдокод
ПК
тогда — да, O(1)
ПК
при любом n
V🇺
я предположил что это псевдокод
питон - новый псевдокод
EZ
питон - новый псевдокод
По скорости работы
V🇺
По скорости работы
и это тоже