Boroda aka Hamster (fantaseour) wrote,
Boroda aka Hamster
fantaseour

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: bing!, cs, tech
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 5 comments