И с динамическим программированием!

From

Oleg I. Khovayko ()

To

All

Date

2002-10-11T21:28:44Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

Проанализировав предыдущую версию своей процедуры
fmask(),  я понял, что в случае длинных строк с большим
количеством звезд и с повторяющимися подстроками 
предыдущая процедура начинат здорово подтормаживать.
Например, если ей сунуть 
mask:[*a*a*a*a*a*a*a*a*b] str:[aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa],
она начинает многократно заниматься всеми возможными перестановками,
и подтормаживает.

Для устранения этого недостатка я модифицировал процедуру, применив 
элементы динамического программирования.
В результате, на длинных и навороченых масках, стало работать
существенно быстрее.

Модифицированая версия - ниже.
Она обладает такими ограничениями:

1. Количество звезд в маске - до 31
2. Максимальная длина строки имени файла - 256.

Мне кажется, что для практического применения
эти ограничения несущественны.

Так что берите и пользуйтесь.
/////////////////////////////////////

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

#define LEN 256

static unsigned long *dp = NULL;

int fmask1(const char *mask, const char *str, unsigned long deep) {
  unsigned long *dp_el = dp + (unsigned char)str;
  
  if(*dp_el & deep) return 0;
  deep <<= 1;
  
  for( ; ; str++) {
    switch(*mask++) {
      case '*' : if(fmask1(mask, str, deep))
                    return 1;
                 mask--;
      case '?' : if(*str == 0) goto ret0;
                 continue;
      case  0  : if(*str == '\0') return 1;
                 goto ret0;
      default  : if((mask[-1] ^ *str) & ~' ') goto ret0;
                 continue;
    } // switch
  } // for

  ret0: *dp_el |= deep >> 1; return 0;
} // fmask

int fmask(const char *mask, const char *str) {
  if(!dp) dp = malloc(LEN * sizeof(unsigned long));
  memset(dp, 0, LEN * sizeof(unsigned long));
  return fmask1(mask, str, 1);
}

void main() {
  char mask[100], str[100];
  const char *rc;
  for( ; ; ) {
    printf("\nEnter mask and str: ");
    scanf("%s%s", mask, str);
    rc = fmask(mask, str)? "OK" : "BAD";
    printf("\nmask:[%s] str:[%s]; Result: %s\n", mask, str, 
    	rc);
  }
}

-- 
#include <best/regards.hpp>
Oleg I. KHOVAYKO  
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
 * Origin: National Center for Biotechnology Information (2:5020/400)