На этом шаге мы рассмотрим алгоритмы, используемые для поиска первого подинтервала.

В организации такого поиска могут помочь следующие алгоритмы:

  ForwardIterator1
  search (ForwardIterator1 beg, ForwardIterator1 end,
          ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
  ForwardIterator1
  search (ForwardIterator1 beg, ForwardIterator1 end,
          ForwardIterator2 searchBeg, ForwardIterator2 sedrchEnd.
          BinaryPredicate op)

Обе формы возвращают позицию первого элемента в первом подинтервале интервала [beg,end), совпадающем с искомым интервалом [searchBeg,earchEnd).

В первой форме элементы найденного подинтервала должны быть равны элементам искомого интервала.

Во второй форме вызов бинарного предиката op(elem,searchElem) для соответствующих элементов искомого интервала и подинтервала должен возвращать true.

Если подходящий элемент не найден, обе формы возвращают end.

Предикат ор не должен изменять свое состояние во время вызова и передаваемые аргументы.

Проблема поиска интервала по известным значениям начального и конечного элементов рассматривается на 99 шаге.

Сложность линейная (не более numberOfElements*numberofSearchElements сравнений или вызовов ор соответственно).

Следующий пример показывает, как найти первое вхождение серии элементов внутри другой последовательности (сравните с примером использования алгоритма find_end() на 275 шаге):

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iterator>
#include "algostuff.hpp"

#include <conio.h> //необходимо для getch()

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;

std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main()
{
  deque<int> coll;
  list<int> subcoll;

  INSERT_ELEMENTS(coll,1,7);
  INSERT_ELEMENTS(coll,1,7);

  INSERT_ELEMENTS(subcoll,3,6);

  PRINT_ELEMENTS(coll,   "Последовательность:\n");
  PRINT_ELEMENTS(subcoll,"Подпоследовательность:\n");
  // Поиск первого вхождения subcoll в coll
  deque<int>::iterator pos;
  pos = search (coll.begin(), coll.end(),         // Интервал
                subcoll.begin(), subcoll.end());  // Подинтервал

  // Цикл повторяется до тех пор, пока внутри coll
  // успешно находится очередное вхождение subcoll
  while (pos != coll.end()) { 
      // Вывод позиции первого элемента
      cout << ToRus("Очередное вхождение подпоследовательности начинается 
                     с элемента ")
           << distance(coll.begin(),pos) + 1
           << endl;

      // Поиск следующего вхождения subcoll
      ++pos;
      pos = search (pos, coll.end(),                  // Интервал
                    subcoll.begin(), subcoll.end());  // Подинтервал
  }


  getch();
  return 0;
}

//---------------------------------------------------------------------------

Текст этого примера можно взять здесь.

Результат выполнения программы:

Рис.1. Результат работы приложения

На следующем шаге мы закончим изучение этого вопроса.

Предыдущий шаг Содержание Следующий шаг