Дискретный анализ ← ЛабораторныеЛабораторная работа №4

Поиск образца в строке

Необходимо реализовать один из стандартных алгоритмов поиска образцов для указанного алфавита.

Упрощенный вариант

Поиск одного образца в тексте с использованием алгоритма Z-блоков. Алфавит --- строчные латинские буквы. На первой строке входного файла образец, на следующей --- текст. Образец и текст помещаются в оперативной памяти. В выходной файл нужно вывести информацию о всех позициях текста, начиная с которых встретились вхождения образца. Выводить следует по одной позиции на строчке, нумерация позиций в тексте начинается с 0.

Пример

Входной файл Выходной файл
  abcaba
  abcabcababcaba
3
8

Варианты алгоритмов

  1. Поиск одного образца при помощи алгоритма Кнута-Морриса-Пратта.
  2. Поиск одного образца при помощи алгоритма Бойера-Мура.
  3. Поиск одного образца при помощи алгоритма Апостолико-Джанкарло.
  4. Поиск одного образца основанный на построении Z-блоков.
  5. Поиск большого количества образцов при помощи алгоритма Ахо-Корасик.
  6. Поиск одного образца-маски: в образце может встречаться «джокер», равный любому другому символу. При реализации следует разбить образец на несколько, не содержащих «джокеров», найти все вхождения при помощcи алгоритма Ахо-Корасик и проверить их относительное месторасположение.

Варианты алфавитов

  1. Слова не более 16 знаков латинского алфавита (регистронезависимые).
  2. Числа в диапазоне от 0 до 232 - 1.

В обоих случаях «джокер» представляется символом ? (знак вопроса).

Формат входных данных

Искомый образец задается на первой строке входного файла.

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

Затем следует текст, состоящий из слов или чисел, в котором нужно найти заданные образцы.

Никаких ограничений на длину строк, равно как на количество слов или числ в них, не накладывается.

Формат выходных данных

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

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

Нумерация начинается с единицы. Номер строки в тексте должен отсчитываться от его реального начала (то есть, без учёта строк, занятых образцами).

Порядок следования вхождений образцов несущественен.

Примеры

Поиск одного образца в алфавите слов:

Входной файл Выходной файл
  cat dog cat dog bird
  CAT dog CaT Dog Cat DOG bird CAT
  dog cat dog bird
1, 3
1, 8

Поиск одного образца с «джокером» в алфавите слов:

Входной файлВыходной файл

  cat ? dog
  cat
  cat
  dog
  dog

1, 1
2, 1

Поиск нескольких образцов в алфавите чисел:

Входной файлВыходной файл

1 2 1 2
1 2 1
2 2 2 2

1 2 1 2 1 2 1 3
2 002 2 02 2

1, 1, 1
1, 1, 2
1, 3, 1
1, 3, 2
1, 5, 2
2, 1, 3
2, 2, 3

Примечание

Запрещается реализовывать алгоритмы на алфавитах меньшей размерности, чем указано в задании.