Из архивов

Нашел тут старую запись.
Суть сводилась к следующей задаче:

Во входном файле две ASCII-строки, одна состоит только из больших латинских букв, в другой могут встречаться большие латинские буквы и еще два спецсимвола - * (звездочка) и ? (знак вопроса). Строки могут иметь длину от 1 до 255 символов, быть в файле в произвольном порядке (но их всего две, формат входных данных корректен). Строку только с буквами назовем словом. Строка со спецсимволами - шаблон, в котором "?" и "*" играют роль символов подстановки по правилам, идентичным wildcards в именах файлов в DOS или Unix-shell, т.е. "?" заменяет собой ровно один произвольный символ, а "*" заменяет собой любое количество произвольных символов - 0 или более (т.е. может заменять и пустую строку). Программа должна выдать ответ YES, если слово подпадает под шаблон (match'ит его), либо NO в противном случае.

Ок. Паттерн-матчинг. Решил "поучаствовать" на время. Заняло минут 15. Получилось вот так вот:

bool match(const char* s,const char* p)

{

    if(!p)return *p==*s;

    if(*p==*s||*p=='?') return match(s+1,p+1);

    while(*s && !match(s++,p+1));

    return *s?true:match(0,p+1);

}

еще минут десять искал ошибку, в результате в код перед while добавилась строчка
if(*p!='*')return false;

красиво (правда проверки на то что строки содержат только большие латинские буквы нет)...можно было бы все лавры себе приписать...если бы не...
Есть такая книжка - Beautiful Code. Одня из статей в ней - как раз и реализация подобного алгоритма на С. Автор статьи - Кернинган, тот самый, брат Ричи. Я кода не помню, но помню одно - было действительно красиво. Красота она в рекурсии... следовательно... см. код. Т.е. алгоритм выстроился в основном по воспоминаниям об этой статье. Даже не столько по воспоминаниям о статье сколько об абстрактных воспоминаниях об ощущениях в процессе цтения. Не читай я эту статью не уверен что до идеи рекурсии дошел бы самостоятельно.
Занятно.

...........
Просмотрел комменты. Наткнулся на:

bool match(const char *word, char const *pattern)

{

    if (!*pattern) return !*word;

    if (*word == *pattern || *pattern == '?') return match(word+1, pattern+1);

    if (*pattern != '*') return false;

    while (*word)  if (match(word++, pattern+1)) return true;

    return match(word, pattern+1);

}

автор кода либо шибко шарит либо тоже читал эту книжку