?

Log in

No account? Create an account
Нэцкэ

MS. Разбор полетов-1

Пока мне не прислали результатов собеседования в MS (наверное уже и не пришлют положительного ответа), проведу разбор не решенных задачек.

Итак задачка про паттерн-матчинг:
Write a function which determines whether provided string matches specified pattern. Signature:
bool is_match(char* text, char* pattern)

Pattern can contain any characters + '*' character which means zero or more characters. For example: is_match("hello", "h*o") returns true; is_match("hello", "hel*lo") also returns true.

Чтобы понять механику решения необходимо понимать работу с конечными автоматами, в чем я имел пробел в знаниях. Наиболее лаконичная теоретическая часть приведена в статье:
Недетерминированные конечные автоматы,

решение конкретно этой задачи через НКА (вширь и в глубь), а также через ДКА есть на форуме RSDN:
http://rsdn.ru/forum/job/4374248.1.aspx

Там же приведено лаконичное решение через рекурсию (по сути это НКА вширь):
match (re,str)
  switch (*re)
    '*': return match(re+1,str) || match(re,str+1)
    '?': return match(re+1,str+1)
    0:   return *str==0
    default: return *re==*str && match(re+1,str+1)
Tags: , ,

Comments

Есть одна хорошая книжка: http://oreilly.com/catalog/9780596510046. В ней есть пример красивого и несложного кода, который делает pattern matching по довольно упрощенным регулярным выражениям.
НКА работает дольше. Иногда существенно дольше. Есть теорема о приведени НКА к ДКА. Всегда стремятся построить ДКА. Автомат лексического анализа (разбора) тем и интересен, что он ДКА, а значит работает за один проход (за один просмотр символа из входного потока без возвратов назад).
совершенно верно. небольшая плата за построение ДКА из НКА окупается тем, что дальше за один проход и строится он один раз, это я понял :)
Я бы не сказал, что плата небольшая. Вычислительная сложность алгоритма CYK (детерминизация автомата) составляет O(N^3). Уже для сотни состояний детерминизация имеет заметно большое время, а для тысячи - лучше поехать в отпуск на пару-тройку недель, а то и на пару месяцев. ;-))
Не всегда. Иногда получается настолько огромный ДКА, что уж лучше битовой маской (маска битов - множество состояний) пройтись по НКА, чем пытаться построить ДКА на гигабайт.