Поиск подпоследовательности в массиве (простой)

Описание

Функция осуществляет поиск первого вхождения массива W в массив T, в результате функция выдает номер первого элемента в массиве T начиная с которого встречается массив W. В случае, если массив W не встречается в массиве T результат функции равен -1.

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

Исходный код

{ массив W с индексами элементов от 0 до M - 1
  массив T с индексами элементов от 0 до N - 1 }
function SimpleSearch (
  W, T: array of byte;
  m, n : LongInt
  ): LongInt;
 
var
     i, j ,k: byte;
     Result: longint;
 
begin
     Result := -2;
     j := 0;
     if m <= n then
     begin
          i := 0;
          repeat
               if W[0] = T[i] then
               begin
                    j := 0;
                    k := i;
                    repeat
                         inc (j);
                         inc (k);
                    until (j >= m) OR (W[j] <> T[k]);
                    if j = m then 
                    begin
                         Result := i;
                         break;
                    end;
               end;
               if (j >= m) OR (i > n - m) then
                  Result := -1;
               inc (i);
          until (Result = -1);
     end;
 
     SimpleSearch := Result;
end;
 
const
     Asize = 2;
     Bsize = 4;
     A: array [0 .. Asize - 1] of byte = (4,8);
     B: array [0 .. Bsize - 1] of byte = (3,4,4,8);
 
begin
     writeln (SimpleSearch (A, B, Asize, Bsize))
end.
 
pascal/search/simple_substring_search.txt · Последние изменения: 2009/10/30 21:00 От romtek
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki