Re: Вопросец возник...

From

Oleg Khovayko ()

To

Evgeniy Jirnov ()

Date

2003-01-28T11:36:11Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>

Evgeniy Jirnov wrote:

> каждой перебирать 3000 строк, тогда можно сильно упростить задачу: во-первых, у
> меня довольно мало масок, где первый символ - "*"

Еще, наверное, у Вас мало масок, где последний символ - "*".
При желании можно создать вторую пару массивов строк и масок,
где строки записаны задом наперед. И опять их отсортировать.
Получите два "префильтра", которые эффективно отбросят
основную массу случаев.

Ну а остальные - прямым перебором, MxN.

Еще один, 3-й, префильтр можно ввести, исходя из след. предположения:
Если в маске присутствует N символов X, и M символов Y, и тп,
то в строке, подходящей под маску, символов X должно быть не
менее, чем N, символов Y должно быть не менее, чем M, и тп.

Но на самом деле, для эффективной реализации последнего префильтра
надо 256 байт на каждую маску и столько же - на каждого кандидата.
Поэтому целесообразность третьего фильтра весьма сомнительна...

 > Но если сделать так, то я получу ограничение на
> 16k строк...

Что-то я не соображу, откуда такое странное ограничение взялось.
Хотя Вам с горы виднее... ;)

>  OK> touch aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
>  OK> ls *a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b
> 
> Гхм... У меня процедура сравнения строки с маской производит довольно мало
> сравнений 

Это _Вы_ так считаете, что мало. Попробуйте в основной while вставить
счетчик, и посмотрите, сколько циклов она накрутит.

> и не валится на такой строчке и маске. 

А не валится потому, что в Вашей процедуре просто есть
дополнительная проверка на совпадение символов в конце
строки/маски. Если в конце маски будет присутствовать
звездочка, эта доп. проверка не сработает, и алгоритм
свалится в факториал.

Попробуйте ей такой вот тест подсунуть:

Str: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Mask: *a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b*

Извините, Паскаля у меня нету, чтобы самому проверить.
А перепирать грамадную процедуру на C лениво.

То есть приведенный Вами алгоритм - из той же серии,
что и UNIX-ная убогость. Отличается только "заплатой",
которая перед тем, как в факториал свалиться,
в конец строки смотрит.

 > Вот ее исходный текст:
Какая-то она большая и запутаная.
И вроде как даже без глюков, за исключением:
  - пустая строка в ней подходит под любую маску.
  - для маски = "*" и пустой входной строки идет попытка
    обращения за левую границу массива маски по
    нулевому индексу.


Ниже - моя процедура fmask1 на C, которая свободна от
указаных выше багов.

/* fmask dynamic procedure
# Wrote by Oleg H. http://olegh.spedia.net
# Oct, 11, 2002
# Version 2
# Distributes according GPL
*
* Limits:
* 1. String lenght < 256
* 2. Stars <= 32
*/

#include <stdio.h>
#include <stdlib.h>

#define LEN 256

static unsigned long dp_stars[LEN];

//---------------------------------------------------------

static int fmask1(const char *mask, const char *str, unsigned long deep) {
   unsigned long *dp_el;
   if(deep == 0) return 0; // Owerflow 32 stars
   for( ; ; str++) {
     switch(*mask++) {
       case '*' : dp_el = dp_stars + (unsigned char)str;
                  if(!(*dp_el & deep) && fmask1(mask, str, deep << 1))
                     return 1;
		 *dp_el |= deep;
                  mask--;
       case '?' : if(*str == 0) return 0;
                  continue;
       case  0  : return *str == 0;
       default  : if(mask[-1] != *str) return 0;
                  continue;
     } // switch
   } // for
} // Function fmask1

//---------------------------------------------------------
void main() {
   char mask[LEN], str[LEN];
   const char *rc;

   for( ; ; ) {
     printf("\nEnter mask and str: ");
     scanf("%s%s", mask, str);
     memset(dp_stars, 0, LEN * sizeof(unsigned long));
     rc = fmask1(mask, str, 1)? "OK" : "BAD";
     printf("\nmask:[%s] str:[%s]; Result: %s\n", mask, str,
     	rc);
   }
}

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)