Comments 39
Не, даже если сколлапсить повторяющиеся звезды, всё равно таймаут:

def isMatch(s,p):
    res=re.match(pat_format(p),s)
    return res is not None

def pat_format(pat):
    pat = re.sub("[*]{2,}", "*", pat)
    pat = re.sub("[?]", ".", pat)
    pat = re.sub("[*]", "(?:.)*?", pat)
    return "^" + pat + "$"
А для Го эта оптимизация работает:
func isMatch(s string, p string) bool {
    res:=strings.Replace(p, "**", "*", -1)
    res1:=strings.Replace(res, "?", ".", -1)
    res2:=strings.Replace(res1, "*", "(?:.)*?", -1)
    r := regexp.MustCompile("^" + res2 + "$")
    return r.MatchString(s)
}


Хм. сперва нарисовало 40ms, потом 68ms, то есть времена нестабильны.

Мне интересно, а зачем вам вообще какая‐либо группировка? * применяется к предыдущему атому, точка — сама по себе атом. Поэтому .* должно нормально зайти. Если добавить ?, то такое решение выдаёт превышение time limit (на моей системе — 8,7 секунд) значительно позже, на тесте 1614:


#!/usr/bin/env python3
import re

class Solution(object):
    @staticmethod
    def isMatch(s,p):
        r = "^"
        for ch in p:
            if ch == '*':
                r += ".*?"
            elif ch=='?':
                r += "."
            else:
                r += ch
        r += "$"
        return bool(re.match(r, s))

# Test 1614
from time import monotonic
start = monotonic()
print(Solution.isMatch("aaabbbaabaaaaababaabaaabbabbbbbbbbaabababbabbbaaaaba", "a*******b"))
print(monotonic() - start)
#  ##test 940
#  import time
#  pt=time.time()
#  print(isMatch("aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba","*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*"))
#  print(time.time()-pt)
Мм… у меня вне зависимости от скобочек вылетает на 1708 / 1808.
коллапс множества звездочек помогает (снижает бэктрэкинг).
Спасибо, действительно убрать повторяющиеся звездочки и указать начало с конец строки это правильно.

Строго говоря, начало строки можно не указывать из‐за match. Вот конец указать нужно, если ответы как‐то принимаются без него, то что‐то с тестами не так.

Все правильно, я сверял первый матч с входной строкой, а указав строго начало конец это и не требуется
Да, времена не повторяются, под виртуалкой, надо несколько раз пробовать,
как вывод — Питон неожиданно медленный…

Кстати, что с жадным, что с нежадным, и в обоих случаях максимально оптимизированном регулярным выражением Python виснет на тесте 1708, хотя тест 1614 уже на моей машине проходит за примерно 0,2 мс независимо от жадности. Вот, собственно, код:


#!/usr/bin/env python3
import re

START = 0
LITERAL = 1
ANY = 2
SOME = 3
MANY = 4
END = 5

class Solution(object):
    @staticmethod
    def isMatch(s, p):
        atoms = [(START,)]
        for ch in p:
            last_atom_typ = atoms[-1][0]
            if ch == '*':
                if last_atom_typ == ANY:
                    atoms[-1] = [MANY, 1]
                elif last_atom_typ == MANY:
                    pass
                elif last_atom_typ == SOME:
                    atoms[-1] = [MANY, atoms[-1][1]]
                else:
                    atoms.append([MANY, 0])
            elif ch=='?':
                if last_atom_typ == MANY:
                    atoms[-1][1] += 1
                elif last_atom_typ == SOME:
                    atoms[-1][1] += 1
                elif last_atom_typ == ANY:
                    atoms[-1] = [SOME, 2]
                else:
                    atoms.append((ANY,))
            else:
                if last_atom_typ == LITERAL:
                    atoms[-1][1] += ch
                else:
                    atoms.append([LITERAL, ch])
        atoms.append((END,))
        atom_to_str_funcs = (
            lambda x: '^',
            lambda x: x[1],
            lambda x: '.',
            lambda x: '.{{{}}}'.format(x[1]),
            lambda x: '.{{{},}}?'.format(x[1]),
            lambda x: '$',
        )
        r = ''.join((
            atom_to_str_funcs[i[0]](i)
            for i in atoms
        ))
        return bool(re.match(r, s))

from time import monotonic
# Test 1614
start = monotonic()
print(Solution.isMatch("aaabbbaabaaaaababaabaaabbabbbbbbbbaabababbabbbaaaaba", "a*******b"))
print(monotonic() - start)
# Test 1708
start = monotonic()
print(Solution.isMatch("abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb", "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"))
print(monotonic() - start)

# Test
#  ##test 940
#  import time
#  pt=time.time()
#  print(isMatch("aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba","*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*"))
#  print(time.time()-pt)

(Для нежадной версии убейте второй вопросительный знак, их здесь всего два.) Я не думаю, что можно сделать что‐то лучше на регулярных выражениях. Вот, кстати, что мой код генерирует для данного теста:


^.{0,}?aa.{0,}?ba.{0,}?a.{0,}?bb.{0,}?aa.{0,}?ab.{0,}?a.{0,}?aaaaaa.{0,}?a.{0,}?aaaa.{0,}?bbabb.{0,}?b.{0,}?b.{0,}?aaaaaaaaa.{0,}?a.{0,}?ba.{0,}?bbb.{0,}?a.{0,}?ba.{0,}?bb.{0,}?bb.{0,}?a.{0,}?b.{0,}?bb$

Да, коллапс вопросов мало поможет в этом тесте, их тут нет :))
а чем `.{0,}?` лучше по сравнению с `.*?`?

Тем, что мне не нужно писать отдельный код для обработки случая [MANY, 0][MANY, 1], которое .+?). Компилятор Python re всё равно должен скомпилировать оба варианта в один и тот же автомат.

Регулярные выражения только в самом простом варианте эквивалентны FSM, не помню где там грань проходит, но нежадные квантификаторы уже добавляют backtracking и это может привксти к очень долгой работе. Да и регулярные выражения это не декларативный подход, просто мини-язык.

Да, ничего не скажу про PCRE, но в регулярках .Net точно используются недетерминированные конечные автоматы в сложных случаях, может быть даже с магазином
По моему, это язык, но не императивный, это не команды или инструкции,
это описание задачи, которую нужно решать, отсюда и производительность может хромать, посмотрите как пример с Го летает
import re
import time

def isMatch(s, p):
    m = re.match(pat_format(p), s)
    if not m:
        return False
    else:
        return m.group() == s


def pat_format(pat):
    pat = re.sub("[*]{2,}", "*", pat)
    pat = re.sub("[?]", ".", pat)
    pat = re.sub("[*]", "(.)*", pat)
    return pat


pt=time.time()
print(isMatch("aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba","*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*"))
print(time.time()-pt)

Спасибо, такой вариант уже опробовали,
Не проходит тест далее:
1708 / 1808 test cases passed.
Status: Time Limit Exceeded
Submitted: 0 minutes ago
Last executed input:
«abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb»
"**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"
Приведенная строка — это полный текст поиска?
В нем нет сочетания такого большого количества `aaaaaaaaa` (хотя и не в нем наверно суть) и нет финишной кавычки.
Дополнительный вопрос: данные в группировках нужны? Они замедляют работу в ~2.5 раза.

Можно заменить:
def pat_format(pat):
    pat = re.sub("\*{2,}", "*", pat)
    pat = re.sub("\?", ".", pat)
    pat = re.sub("\*", ".*", pat)
    return pat
Поправка, нашел весь текст в исходном коде.
Просто не отображается вся строка в тексте комментария по длине.
При использовании регулярных выражений из стандартной библиотеки, к сожалению, действительно долго. На этом выражении запнулся на ~5 минутах.
Но при использовании пакета regex, скорость выполнения ~0.066 сек. Но, как я понял, его нельзя импортировать.
Прошу прощения, это ответ на этот комментарий.
Нашел решение с использованием регулярных выражений, но в комбинации с разбиением исходного выражения по `*` и отсечением исходной строки по каждому из них.

class Solution:
    start_p = re.compile("\*+")
    q_p = re.compile("\?")

    def isMatch(self, s: str, p: str):
        test_s = s
        pattern_list = list(filter(None, self.pat_format(p).replace('.*?', '\n.*?').split('\n')))
        pattern_len = len(pattern_list)
        last_index = pattern_len - 1

        for index, pattern in enumerate(pattern_list):
            if index == last_index:
                pattern = pattern + '$'

            m = re.match(pattern, test_s)
            if not m:
                return False

            test_s = test_s[m.span()[1]:]

        return not bool(test_s)

    def pat_format(self, pat: str):
        pat = self.q_p.sub(".", pat)
        pat = self.start_p.sub(".*?", pat)
        return pat


Вроде получился неплохой результат, лучший прогон: 108 Runtime (ms).
Your runtime beats 87.06 % of python3 submissions.
В Python версии проблема в катастрофическом откате. Надо бы паттерн "(.)*" заменить на ".*+" — сверхжадный квантификатор. Вот только пайтона у меня нет чтобы проверить, на перле это работает.

Если интересны подробности — habr.com/post/56765
«sre_constants.error: multiple repeat»
а если в скобки завернуть (.*)+ — «Time Limit Exceeded» еще раньше

re не поддерживает их (regex да, но он недоступен).
можно поиграться с negative lookahead's чтоб избавиться от отката назад.

AI-Vadim выше реализовал их отдельными запросами, что не совсем спортивно :D
А fnmatch никто не пробовал?
>>> import time
>>> start = time.time(); fnmatch.fnmatch('aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba', '*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*'); time.time() - start
True
816.2632331848145
>>>
Не, эффект тот же: 1708 / 1808 test cases passed.
Time Limit Exceeded

«abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb»
"**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"

Если вы наберёте в iPython import fnmatch, затем fnmatch??, то увидите, что fnmatch делает ровно то же самое, что и ряд людей выше, включая меня: преобразует шаблон в регулярное выражение.

И еще возможно стоило бы попробовать re2, он детерминированный насколько я понимаю.
Хмм, странно, вроде был под питон, а сейчас не ставится. Ну ладно тогда.

Хотел бы про скобки сказать.
Скобки нужны как для описания регекспа, так и для разметки групп.


Движок не знает, что вы от него хотите тупо проверить "матчится или нет", а не "что с чем матчится".
Поэтому лучше использовать non-capturing group (?: sub-expression-goes-here ) — как посоветовали в первом комментарии (без объяснений, правда).


А в случае со звёздочкой .* — вообще непонятно, зачем было вводить группу. Квантификатор же относится ровно к предшествующему терму.

Регекспы с кучей звёздочек внутри не могут не тупить на "плохих" строках, если только не приложить специальные усилия.
Потому что:
1) там работают откаты
2) регекспы — детерминированные, там не просто "что-то с чем-то сматчилось", а "сматчилось лексикографически первое в рамках жадности/ленивости квантификаторов".
Поэтому накаты и откаты там последовательные.


Как, кстати, и в наивной реализации матчилки на прологе.


Как можно оптимизировать матчилку?
Ну, например, сделать очевидную проверку:
набор_букв(строки) ⊇ набор_букв(образца без глоб-символов)


% первый аргумент - надпоследовательность второго
is_supersequence(_, []).
is_supersequence([C|S], [C|P]) :- is_supersequence(S, P).
is_supersequence([_|S], P) :- is_supersequence(S, P).
% (вроде бы не налажал...)

% слабое условие: если fail, то наверняка test_pattern провалится
can_match(S, P) :- filter(is_letter, P, LP), is_supersequence(S, LP).

test_whole_pattern(S, P) :- can_match(S, P), test_pattern(S, P).
% а дальше как с гусём

Теоретически, такую проверку можно было бы втыкать на каждом рекурсивном вызове test_pattern после того, как звёздочка или вопросик откусили символ строки.
Но тогда мы на ровном месте поднимем квадратичную сложность по заветам маляра Шлемюэля. А оно надо?


Значит, требуется перейти к каким-то структурам и проверкам, которые инкрементно сохраняют проверку на надпоследовательность.
Тут мне надо подумать, я этот труд ещё не проделал. Поэтому — только наброски.


  • построить мультимножества букв строки и образца; при откусывании буквы из строки — декрементировать счётчик вхождений в строку и смотреть, что он не стал меньше счётчика вхождений в образец; при откусывании буквы из образца — просто декрементировать счётчик вхождений в образец. Это будет быстро работать, если в прологе есть структура данных "вектор / хештаблица". Если нет — то сперва велосипедить…
    test_pattern(S, MultisetOfS, P, MultisetOfP)
  • параллельно сопоставлению с образцом выполнять сопоставление с набором букв образца
    test_pattern(S, P, LettersOfP)
    то есть, мы знаем, какая буква будет следующей в образце, и соответственно делать более агрессивные проверки и/или предпочтительные ветвления
Плюсую,
«вектор / хештаблица» в прологе только как динамические факты,
типа:
:-dynamic hash/2. - объявление в начале
assert(hash(Key,Value)) - добавление
hash(Key,Value) - проверка
retract(hash(Key,Value)), assert(hash(Key,NewValue)) - замена значения (в реализации Visual Prolog есть особые single факты их можно не удалять)

Но assert() это побочный эффект, использование глобального контекста, не очень чисто…

В этой попытке решения интересный результат получился с Го, при одинаковых условиях скорость порядочна.
Only those users with full accounts are able to leave comments. Log in, please.