1) Убирать повторяющиеся '?' не корректно.
2,3) Если я правильно понимаю, ваш is_match при встрече '*' начинает перебирать все комбинации суффиксов строки и паттерна и сопоставлять их, в структуру дерева же эта звёздочка не кодируется. У меня же звездочки закодированы в структуру дерева в виде реккурентных связей (так что это уже не дерево, а граф в общем виде) NFA. После детерминизации время прохода по DFA пропорционально длине строки и не зависит от наличия звездочек.
'?'не корректно.2,3) Если я правильно понимаю, ваш
is_matchпри встрече'*'начинает перебирать все комбинации суффиксов строки и паттерна и сопоставлять их, в структуру дерева же эта звёздочка не кодируется. У меня же звездочки закодированы в структуру дерева в виде реккурентных связей (так что это уже не дерево, а граф в общем виде) NFA. После детерминизации время прохода по DFA пропорционально длине строки и не зависит от наличия звездочек.Именно. И неплохо было бы заранее их (объёмы) объявлять, вместе с остальными правилами конкурса.