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 Freq[ASIZE];
   
   /* 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);
   }
   
   /* Optimal Mismatch pattern comparison function. */
   int OPTIMAL_PCMP(PAT *pat1, PAT *pat2)
   {
    float fx;
   
    fx=Freq[pat1->loc]-Freq[pat2->loc];
    return(fx ? (fx > 0 ? 1 : -1) : (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 delta 2 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;
    }
   }
   
   /* Optimal Mismatch string matching algorithm. */
   void OM(char *y, char *x, int n, int m)
   {
    int i, j, td2[XSIZE], td1[ASIZE];
    PAT pattern[XSIZE];
   
    /* Preprocessing */
    ORDER_PATTERN(x, m, OPTIMAL_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
Автор проекта: Эксклюзивные курсы программирования