Занимательный пролог #3

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

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)

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

>>> 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
>>>

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

Движок не знает, что вы от него хотите тупо проверить "матчится или нет", а не "что с чем матчится".
Поэтому лучше использовать 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)
  то есть, мы знаем, какая буква будет следующей в образце, и соответственно делать более агрессивные проверки и/или предпочтительные ветвления