Delphi World - Точный поиск подстроки в строке - Алгоритм максимального сдвига
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Точный поиск подстроки в строке - Алгоритм максимального сдвига

Автор: Thierry Lecroq
Перевод: Кантор И.

Вариант алгоритма быстрого поиска, просматривающий символы образца от соответствующего наибольшему сдвигу к наименьшему.

Реализация на Си

   typedef struct pattern_scan_order {
      int loc;
      char c;
   } PAT;
   
   int MinShift[XSIZE];
   
   /* Computation of the MinShift table values. */
   void COMPUTE_MINSHIFT(char *x, int m)
   {
    int i, j;
   
    for (i=0; i < m; i++) {
       for (j=i-1; j >= 0; j--)
           if (x[j] == x[i]) break;
       MinShift[i]=i-j;
    }
   }
   
   /* Construct an ordered pattern from a string. */
   void ORDER_PATTERN(char *x, int m, int (*pcmp)(), PAT *pattern)
   {
    int i;
   
    for (i=0; i <= m; i++) {
       pattern[i].loc=i;
       pattern[i].c=x[i];
    }
    qsort(pattern, m, sizeof(PAT), pcmp);
   }
   
   
   /* Maximal Shift pattern comparison function. */
   int MAXSHIFT_PCMP(PAT *pat1, PAT *pat2)
   {
    int dsh;
   
    dsh=MinShift[pat2->loc]-MinShift[pat1->loc];
    return(dsh ? dsh : (pat2->loc-pat1->loc));
   }
   
   
   /* Constructs the delta 1 shift table from a pattern string. */
   void BUILD_TD1(char *x, int m, int *td1)
   {
    int a, j;
   
    for (a=0; a < ASIZE; a++) td1[a]=m+1;
    for (j=0; j < m; j++) td1[x[j]]=m-j;
   }
   
   
   /* Find the next leftward matching shift for the first ploc pattern */
   /*  elements after a current shift or lshift.                       */
   int MATCHSHIFT(char *x, int m, int ploc, int lshift, PAT *pattern)
   {
    int i, j;
   
    for (; lshift < m; lshift++) {
       i=ploc;
       while (--i >= 0) {
          if ((j=(pattern[i].loc-lshift)) < 0) continue;
          if (pattern[i].c != x[j]) break;
       }
       if (i < 0) break;
    }
    return(lshift);
   }
   
   
   /* Constructs the delta2 shift table from an ordered string. */
   void BUILD_TD2(char *x, int m, int *td2, PAT *pattern)
   {
    int lshift, i, ploc;
   
    td2[0]=lshift=1;
    for (ploc=1; ploc <= m; ploc++) {
       lshift=MATCHSHIFT(x, m, ploc, lshift, pattern);
       td2[ploc]=lshift;
    }
    for (ploc=0; ploc <= m; ploc++) {
       lshift=td2[ploc];
       while (lshift < m) {
          i=pattern[ploc].loc-lshift;
          if (i < 0 || pattern[ploc].c != x[i]) break;
          lshift++;
          lshift=MATCHSHIFT(x, m, ploc, lshift, pattern);
       }
       td2[ploc]=lshift;
    }
   }
   
   /* Maximal Shift string matching algorithm. */
   void MS(char *y, char *x, int n, int m)
   {
    int i, j, td2[XSIZE], td1[ASIZE];
    PAT pattern[XSIZE];
   
    /* Preprocessing */
    COMPUTE_MINSHIFT(x ,m);
    ORDER_PATTERN(x, m, MAXSHIFT_PCMP, pattern);
    BUILD_TD1(x, m, td1);
    BUILD_TD2(x, m, td2, pattern);
   
    /* Searching */
    i=0;
    while (i <= n-m) {
       j=0;
       while (j < m && y[i+pattern[j].loc] == pattern[j].c) j++;
       if (j >= m) OUTPUT(i);
       i+=MAX(td1[y[i+m]], td2[j]);
    }
   }
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования