Проектирование параллельных алгоритмов в задачах идентификации. Вашкевич Н.П - 7 стр.

   конечно, выполнить преобразование, раскрыв скобки, но тогда суффиксы и префиксы
   уйдут в каждую из трех цепочек, что увеличит размерность алгоритма.

  5) Поиск цепочек, когда во входной последовательности некоторые символы яв-
   ляются "прозрачными" (т.е. их как бы нет). Например, игнорирование знаков пре-
   пинания в тексте или определенных байтовых комбинаций в двоичных файлах.

  6) Когда поиск во входной последовательности начинается по сигналу "извне", а
   до того времени на каждом шаге осуществляется просто прием очередного символа
   входной последовательности. Например, когда поиском управляет внешняя среда или
   когда нужно найти цепочку после пропуска определенного количества символов
   входной последовательности.

   Отметим, что начальное состояние s0 НДКА, которое назовем маркером начала поис-
ка имеет очень существенное значение. Маркер позволяет динамически управлять про-
цессом поиска без изменения самого алгоритма поиска (программная или аппаратная реа-
лизация не меняется), что обеспечивает гибкость при реализации алгоритма. Например,
не меняя алгоритма, а управляя только маркером можно получить решение следующих
подзадач, которые могут являться составной частью задач 1-6.
   1) Не начинается ли входная последовательность с искомых цепочек, т е. самый пер-
   вый символ последовательности совпадает с первым символом цепочки. Это может
   потребоваться если производится такой поиск во многих файлах или даже в том слу-
   чае если это поиск в одном файле ( который в принципе можно сделать вручную), но
   цепочка достаточно длинная (сотни и более байт) и тогда возможна ошибка из-за че-
   ловеческого фактора. Такая задача решается установкой маркера начала поиска ( s0=1
   ) перед приемом входной последовательности и сбросом его ( s0=0 ) после приема
   первого символа.

  2) Классическая задача поиска, когда входная последовательность может содержать
   цепочки в любом месте между "top" и "bottom". Эта задача решается установкой мар-
   кера ( s0=1 ) перед приемом входной последовательности, без последующего сброса
   (поиск искомых цепочек начинается с каждого очередного символа).

  3) Поиск во входной последовательности начинается после поступления в ней опре-
   деленного символа или символов (точки, отмечающей конец предложения и т.п.). Эта
   задача решается установкой маркера после поступления этого символа, без после-
   дующего сброса.




                                          7