Блог пользователя PanZverski

Автор PanZverski, 13 лет назад, По-русски

Привет.
Наверняка, кто-нибудь тут сталкивался с задачей проверки строки на соответсвие шаблона заданного Wildcard, на манер имен файлов (c:\dir\*\????la*.txt). То есть: * - любое количество символов, ? - один любой символ.
Первое, что мне пришло в голову - это жадный алгоритм решения.

Разделяем всю строку на группы между которыми стоят *. Ищем каждую группу, как можно ближе к началу строки.

Ситуации типа: *??*?*  - обрабатываем как одну *, но пропускаем 3 символа в строке.
При поиске последней группы требуем чтобы она находилась в конце строки.

Вот код: http://pastebin.com/ALQa7WmE

И вроде бы, я не могу найти контр-примера. Но в интернете везде лежит либо, некорректный жадный алгоритм, не обрабатывающий ситуации a*? или же динамика.  Может кто-нибудь привести контр-пример?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор PanZverski, 15 лет назад, По-русски
да, это все только про С.

почему-то мне кажется, что авторское решение не верно. и, в связи с этим, странно, каким образом, так много людей ее сдало...
+ обидно, что слил контест из-за такой подставы...

было примерно так.
сдаю задачу А.
читаю Б, понимаю что думать тут нечего, только писать быстро и точно. написал половину, примерно, стало скучно.
думаю, дай почитаю что дальше, может быть, там задачи по-интереснее. действительно, задача С. звучит интересно, и решение пришло короткое. написал минут за 10. отправляю - ВА 8.
потом, пытаюсь понять в чем дело...
так прошло минут еще 40...
в итоге бросил, расстроился, дописал Б. но так и не смог ее сдать, видимо, баги.
контест, кончился.

сейчас, думаю что я все-таки правильно решил С.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

Автор PanZverski, 15 лет назад, По-русски
возникла такая идея.
сделать аналогично topcoder-у предварительную проверку при отправке задачи... ну, то-есть прогнать решение на сэмплах, или же во время тестирования, если задача не проходит первые один-два теста, эквивалентные сэмплам - минус не ставить.
просто, учитывая формат проводимых тут раундов (немного задач, много людей, мало времени), один минус может отодвинуть сразу мест на 10-20...
обидно, когда так получается из-за того, что забыл сохраниться в среде... или же, в спешке выбрал не тот файл...

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор PanZverski, 15 лет назад, По-русски
Кто нибудь знает решение за O(n) ?

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится