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

  • wordpress: php -> nodejs

    Хипстеры захватывают мир :) Не очень понятно, как этот переход отразится, на людях, которые ставят этот вордпресс на любой копеечный хостинг с…

  • ultimate php

    For those who asked how to get started testing PHP7. I have packaged up my dev environment in a Vagrant box: https://t.co/EOhyi17fPI— Rasmus…

  • Ruby и IoC

    Ковыряюсь в руби. Появился некоторый навык и теперь хочется докопаться до подробностей. Полез посмотреть, как там с моей навязчивой идеей об IoC.…

  • 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