ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg I. Khovayko                     2:5020/400     11 Oct 2002  21:28:44
 To : All
 Subject : И с динамическим программированием!
 -------------------------------------------------------------------------------- 
 

 Проанализировав предыдущую версию своей процедуры
 fmask(),  я понял, что в случае длинных строк с большим
 количеством звезд и с повторяющимися подстроками 
 предыдущая процедура начинат здорово подтормаживать.
 Hапример, если ей сунуть 
 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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор