LINUX.ORG.RU

Wildcards


0

0

У кого есть алгоритм для работы с wildcards? Вообщем, нужно только одно - функций wild_strcmp(str, wildcard) возвращающая 0 в случае совпадения str с wildcard, и >0 в случае несовпадения. Мне нужна обработка как минимум *, ?, и [...].

Re: Wildcards

Для (*,?) есть очевидный алгоритм с динамическим программированием за

O(len str * len pattern)

Пусть F[i,j] - функция равная true если начальный префикс длиной i, соответствует начальному префиксу длины j из шаблона. Нужно аккурантно выразить F[i,j] через F[i-1,j-1],F[i-1,j], F[i,j-1] c учотом граничных условий и заполнить массив

Для общих регексвов можно построить за возможно экпонтенциальное время конечный автомам а затем ла линейное проверить соответствие, либо попытаться решать динамическим программированием (получится полином от размера str и шаблона).

А еще есть готовые библиотеки.

ival ★★ ()

Re: Wildcards

видимо man 3 fnmatch

int fnmatch(const char *pattern, const char *string, int flags);

The fnmatch() function checks whether the string argument matches the pattern argument, which is a shell wildcard pattern.

MKuznetsov ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.