При запуске программы пользователю предлагается ввести параметры для генерации первой строки:

1) Длина периода.

2) Кратность периода.

3) Смещение периода (указывается, чтобы период начинался не с начала строки).

4) Длина строки.

Во время ввода проверяется корректность вводимых данных, отсеиваются отрицательные значения и значения длины, меньшие минимально возможного (Смещение + Длина периода * Кратность периода).

После окончания процесса генерации первой строки данные записываются в файл «S1.txt», а пользователю, для генерации второй строки, предлагается ввести количество отличий второй строки от первой.

После ввода указанное количество случайных элементов второй строки заменяется новыми, при этом проверяется, чтобы несколько раз не был изменен один и тот же элемент, а так же, что генератор случайных чисел выдал новое случайное число, не равное уже существующему элементу. Данные проверки гарантируют, что вторая строка будет иметь то количество отличий, которое указал пользователь. После окончания процесса генерации второй строки данные записываются в файл «S2.txt» и программа заканчивает свою работу.

3.4 Инструкция пользователю

Программа StringGenerator создает строки с заданными характеристиками. В ней можно задать: длину строки, длину периода, кратность периода, смещение периода, количество отличий второй строки от первой. Результат работы записывается в текстовый файл S1 или файлы S1и S2. При запуске пользователю будет предложено ввести длину периода, затем кратность, смещение периода относительно начала строки, длину строки и количество отличий второй строки от первой (Рисунок 25).

Рисунок 25 - Диалоговое меню программы StringGenerator

Все алгоритмы анализа строк реализованы в основной программе. Программа имеет реализацию на 2 языках программирования: С и Pascal. Программа на С написана с использованием стандарта С-99. При запуске пользователю будет предложено выбрать конкретный алгоритм для выполнения или вычислить все.

Диалоговое меню программы на языке С (Рисунок 26):

Рисунок 26 - Диалоговое меню программы на языке С

Диалоговое меню программы на языке Pascal (Рисунок 27):

Рисунок 27 - диалоговое меню программы на языке Pascal

Необходимо ввести число от 1 до 4 для выполнения определенной задачи или задач:

1. При вводе 1 будет вычислена LCS.

2. При вводе 2 будет вычислено расстояние Левенштейна.

3. При вводе 3 будет найден период максимальной длины и его кратность, так дополнительно необходимо указать для какой строки необходимо выполнить поиск: необходимо ввести 1 для поиска в первой строке, 2 для поиска во второй.

4. При вводе 4 будет вычислено расстояние Левенштейна, найдена LCS и наибольший период и его кратность. Так же необходимо уточнение в какой из строк следует искать период: вводится 1 для поиска в 1 строке, 2 для поиска во второй.

Данные на вход программе должны подаваться в виде файлов, содержащих пары чисел (State_i, s_i), где s_i - момент системного времени, в который произошло i-е событие в модели, State_i - состояние системы в этот момент (целое положительное число). Рекомендуется, чтобы каждая пара чисел находилась в новой строке. Файлы должны называться S1.txt и S2.txt для первой и второй строки соответственно.

После завершения работы программы результаты будут помещены в файл или файлы. Результат нахождения:

a) редакционного расстояния будет находиться в файле EditDinst.txt (Рисунок 28).

Рисунок 28 - Результат вычисления расстояния Левенштейна

b) наибольшей общей подпоследовательности в файле LCS.txt (Рисунок 29).

Рисунок 29 - Результат вычисления LCS

c) максимального периода максимальной кратности в файле Period.txt (Рисунок 30).

Рисунок 30 - результат вычисления периодической структуры

При новом запуске программы все старые файлы решений будут удалены.

3.5 Примеры работы программы

Примеры работы программы будут приведены на строках небольшого размера (40-80 символов) для наглядности и возможности оценки корректности вычислений.

Вычисление расстояния Левенштейна.

1) Строки совпадают.

Первая строка (Рисунок 31):

Рисунок 31 - первая строка

Вторая строка (Рисунок 32):

Рисунок 32 - вторая строка

Результат вычислений (Рисунок 33):

Рисунок 33 - результат вычисления расстояния Левенштейна

1) Строки абсолютно разные.

Первая строка (Рисунок 34):

Рисунок 34 - первая строка

Вторая строка (Рисунок 35):

Рисунок 35 - вторая строка

Результат вычислений (Рисунок 36):

Рисунок 36 - результат вычисления расстояния Левенштейна

2) Строки частично разные, длина строк совпадает.

Первая строка (Рисунок 37):

Рисунок 37 - первая строка

Вторая строка (Рисунок 38):

Рисунок 38 - вторая строка

Результат вычислений (Рисунок 39):

Рисунок 39 - Результат вычисления расстояния Левенштейна

Строки частично разные, длина строка разная.

Первая строка (Рисунок 40):

Рисунок 40 - Первая строка

Вторая строка (Рисунок 41):

Рисунок 41 - Вторая строка

Результат вычислений (Рисунок 42):

Рисунок 42 - Результат вычисления расстояния Левенштейна

Нахождение наибольшей общей подпоследовательности.

1) Строки совпадают.

Первая строка (Рисунок 43):



Рисунок 43 - Первая строка

Вторая строка (Рисунок 44):

Рисунок 44 - Вторая строка

Результат вычислений (Рисунок 45):

Рисунок 45 - Результат вычисления LCS

2) Строки абсолютно разные.

Первая строка (Рисунок 46):

Рисунок 46 - Первая строка

Вторая строка (Рисунок 47):

Рисунок 47 - Вторая строка

Результат вычислений (Рисунок 48):

Рисунок 48 - Результат вычисления LCS

3) Строки частично разные, длина строк совпадает.

Первая строка (Рисунок 49):

Рисунок 49 - Первая строка

Вторая строка (Рисунок 50):

Рисунок 50 - Вторая строка

Результат вычислений (Рисунок 51):

Рисунок 51 - Результат вычисления LCS

4) Строки частично разные, длина строк разная.

Первая строка (Рисунок 52):

Рисунок 52 - Первая строка

Вторая строка (Рисунок 53):

Рисунок 53 - Вторая строка

Результат вычислений (Рисунок 54):

Рисунок 54 - Результат вычисления LCS

Нахождения периода максимальной кратности.

1) Период кратности более 2 не встречается в строке

Строка (Рисунок 55):

Рисунок 55 - Первая строка

Результат вычислений (Рисунок 56):

Рисунок 56 - Результат вычисления периодической структуры

2) В строке только один максимальный период

Строка (Рисунок 57):

Рисунок 57 - Строка, в которой необходимо найти период максимальной длины

Результат вычислений (Рисунок 58):

Рисунок 58 - Результат вычисления периодической структуры

3) В строке несколько периодов максимальной длины

Строка (Рисунок 59):



Рисунок 59 - Строка, в которой необходимо найти период максимальной длины

Результат вычислений (Рисунок 60):

Рисунок 60 - Результат вычисления периодической структуры

Заключение

В ходе работы были рассмотрены различные алгоритмы решения каждой из задач. Был проведен сравнительный анализ этих алгоритмов. Для каждой из задач был реализован один алгоритм, менее требовательный к памяти. Программа была реализована на 2 языках программирования: Pascal и C.

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

Список использованных источников

1. Смит Б. Методы и алгоритмы вычислений на строках. - М.: ООО «И.Д. Вильямс», 2006.

2. The String-to-String Correction Problem / Robert A. Wagner, Michael J. Fischer - Journal of the ACM Volume 21 Issue 1, Jan. 1974, Pages 168-173

3. http://neerc.ifmo.ru/wiki/index.php? title=Основные_определения,_связанные_со_строками

4. Строгалев В.П., Толкачева И.О. Имитационное моделирование. - МГТУ им. Баумана, 2008.

5. Толстуев Ю.И., Планковский С.И. Моделирование и симуляция логических систем. Курс лекций. Харьковский авиационный институт. 2009.

6. Baeza-Yates R.A. (1989b) «String searching algorithms revisited,» Lecture Notes in Computer Science, Vol. 382, p. 75-96.

7. http://habrahabr.ru/post/142825/

8. http://ru.wikipedia.org/wiki/PascalABC.NET

9. Беллман Р. Динамическое программирование. - М.: Изд-во иностранной литературы, 1960.

10. String Search / Graham A Stephen - October 1992.

11. http://ru.wikipedia.org/wiki/Visual_Studio

Приложение

Код основной программы на языке Pascal

type

IntArray = array of longint;

IntMatrix = array of array of longint;

var

file1: text;

S1, S2: IntArray; // Строки

Length1, Length2: longint; // Длины строк

SEQ: IntArray; // НОП и всп. массив

mode, strNum: integer;

// Поиск минимального значения

function Min (X: integer; Y: integer): integer;

begin

if X < Y then Min:= X

else Min:= Y;

end;

// Поиск максимального значения

function Max (X: integer; Y: integer): integer; begin

if X > Y then Max:= X

else Max:= Y;

end;

// Поиск подстроки в строке

function SubString (STR: IntArray; SubSTR: IntArray; FirstIndex: longint): longint;

var

i, j, LastIndex: longint;

isFind: boolean;

begin

SubString:= -1; // Изначально вхождение не найдено

LastIndex:= Length(STR) - Length(SubSTR);

if (FirstIndex <= LastIndex) Then

for i:= FirstIndex to LastIndex do

begin

isFind:= true;

for j:= 0 to SubSTR. Length - 1 do

if (SubSTR[j] <> STR [i + j]) then isFind:= false;

if (isFind) then

begin

SubString:= i;

break;

end;

end;

end;

// Процедура, считывающая значения массива из файла

procedure ReadFromFile (file1: text; path: string; var S: IntArray);

var A: integer;

c: char;

Length: longint;

i: longint;

begin

assign (file1, path);

reset(file1);

Length:= 0;

while (not eof(file1)) do // Придется полностью просматривать файл

begin // т.к. FileSize работает некорретно

while (c = ' ') do

read (file1, c);

read (file1, c);

A:= (ord(c) - 48);

read (file1, c);

while (c <> ' ') do

begin

A:= A * 10 + (ord(c) - 48);

read (file1, c);

end;

INC(Length);

read (file1, c);

if (eof(file1)) then break;

read (file1, c);

while (c <> #13) do

read (file1, c);

read (file1, c);

end;

reset(file1);

setLength (S, Length); // Выделяем память под массив

i:= 0;

while (not eof(file1)) do // Придется полностью просматривать файл

begin // т.к. FileSize работает некорретно

while (c = ' ') do

read (file1, c);

read (file1, c);

A:= (ord(c) - 48);

read (file1, c);

while (c <> ' ') do

begin

A:= A * 10 + (ord(c) - 48);

read (file1, c);

end;

S[i]:= A;

read (file1, c);

if (eof(file1)) then break;

read (file1, c);

while (c <> #13) do

read (file1, c);

read (file1, c); // Сам символ перевода каретки

INC(i);

end;

close(file1);

end;

// Процедура, инициализирующая подпоследовательность

// Изначально заполняет НОП -1-ми, т.е. НОП - пуста

procedure InitSEQ();

var j: longint;

begin

Length1:= Length(S1);

Length2:= Length(S2);

if (Length1 < Length2) then // Длина C - минимум из M и N (приходится

begin // брать с запасом, т.к. пока мы не знаем

SetLength (SEQ, Length1); // длину НОП

for j:= 0 to Length1 - 1 do

SEQ[j]:= -1; // -1 показывает конец НОП,

end // изначально НОП пуста

else

begin

SetLength (SEQ, Length2);

for j:= 0 to Length2 - 1 do

SEQ[j]:= -1;

end;

end;

// Процедура, вычисляющая вектор, равный последней строке матрицы НОП

// Входные параметры: X - первая строка, Y - вторая строка, LL - массив,

// в который будет помещен результат

procedure LCS_LENGTH (M: integer; N: integer; X: IntArray; Y: IntArray; var LL: IntArray);

var

i, j: longint; // Итерационные счетчики

H: IntMatrix; // Двумерный массив, хранящий i-ю и (i-1) - ю строки матрицы НОП

begin

SetLength (H, 2); // Устанавливаем размер открытого массива H

SetLength (H[0], N + 1);

SetLength (H[1], N + 1);

for i:= 0 to N do // Инициализируем 2-ю строку массива H

H [1, i]:= 0;

for i:= 0 to M - 1 do // Вычисляем H

begin

for j:= 0 to N do // Сдвигаем вторую строку вверх

H [0, j]:= H [1, j];

for j:= 0 to N - 1 do // Само вычисление

if (X[i] = Y[j]) then H [1, j + 1]:= H [0, j] + 1

else H [1, j + 1]:= Max (H[1, j], H [0, j + 1]);

end;

for j:= 0 to N do // Копируем результат в выходной вектор

LL[j]:= H [1, j];

end;

// Нахождение максимального периода максимальной кратности

procedure FindMaxPeriod (STR: IntArray);

var

SubSTR: IntMatrix; // Матрица подстрок текущей длины

MaxCurrMult: IntArray; // Массив максимальных кратностей для подстрок текущей длины

PeriodLength, offset, index, prev_index, i, j: longint;

MaxMult, CurrMult: longint;

AlreadyWas: boolean;

begin

PeriodLength:= Length(STR) div 2;

MaxMult:= 1;

while (PeriodLength > 0) do // Начинаем с подстрок большей длины. Если находим период с кратностью >1, то закончили

begin

SetLength (SubSTR, Length(STR));

SetLength (MaxCurrMult, Length(STR));

offset:= 0;

while ((Length(STR) - (offset + 2 * PeriodLength)) + 1 > 0) do // Если в строке осталось меньше элементов, чем в подстроке, то берем след.

begin

SetLength (SubSTR[offset], PeriodLength);

index:= 0;

CurrMult:= 1;

MaxCurrMult[offset]:= 1;

for i:= 0 to PeriodLength - 1 do

SubSTR [offset, i]:= STR [i + offset];

prev_index:= SubString (STR, SubSTR[offset], 0);

while (index <> -1) do // Поочередно ищем вхождения, определяя, период это или нет.

begin

index:= SubString (STR, SubSTR[offset], prev_index + 1);

if (index = prev_index + PeriodLength) then

begin

INC(CurrMult);

if (CurrMult > MaxCurrMult[offset]) then MaxCurrMult[offset]:= CurrMult;

end

else CurrMult:= 1;

prev_index:= index;

end;

if (MaxCurrMult[offset] > MaxMult) then MaxMult:= MaxCurrMult[offset];

INC(offset);

end;

if (MaxMult > 1) then break;

DEC(PeriodLength);

end;

assign (output, 'Period.txt');

rewrite(output);

if (MaxMult < 2) then

writeln ('Периодов кратности не менее 2 в исходной строке нет')

else

begin

writeln ('Максимальный период: ', Length (SubSTR[0]));

writeln ('Кратность периода: ', MaxMult);

j:= 0;

for offset:= 0 to Length(STR) do

begin

try

begin

AlreadyWas:= false;

if (MaxCurrMult[offset] = MaxMult) then

begin

for i:= 0 to offset - 1 do

if (SubString (SubSTR[i], SubSTR[offset], 0) <> -1) then AlreadyWas:= true;

if (AlreadyWas) then continue;

INC(j);

writeln ('Период #', j, ':');

for i:= 0 to Length (SubSTR[offset]) - 1 do

write (SubSTR[offset, i], ' ');

writeln();

end;

end;

except

begin

close(output);

break;

end;

end;

end;

end;

try

close(output);

except

end;

end;

// Процедура, вычисляющая НОП

procedure LCS (M: integer; N: integer; X: IntArray; Y: IntArray; var C: IntArray);

var

i, j, k: longint; // Итерационные счетчики

L1, L2: IntArray; // Последнии строки матрицы H

SUB_X, SUB_Y: IntArray; // Подстроки

C1, C2: IntArray;

notEmpty: boolean; // Флаг непустой подпоследовательности

Found: boolean; // Флаг нахождения y_index

x_index: longint; // Индекс деления строки X

y_index: longint; // Индекс деления строки Y

last_i: longint; // переменная, для индекса последнего элемента SUB_X

lcs_max: longint; // максимальная L1j + L2n-j

begin

i:= 0; // Инициализация для цикла While

SetLength (L1, N + 1);

SetLength (L2, N + 1);

notEmpty:= false;

if ((M = 0) or (N = 0)) then // Тривиальный случай

C[0]:= -1

else if (M = 1) then

begin

while ((notEmpty <> true) and (i < N)) do

begin

if (X[0] = Y[i]) then

notEmpty:= true;

INC(i);

end;

if (notEmpty = true) then C[0]:= X[0] // Если НОП не пуста, присваиваем ед. возможное значение

else C[0]:= -1; // Иначе - код ошибки

end

else if (N = 1) then

begin

while ((notEmpty <> true) and (i < M)) do

begin

if (Y[0] = X[i]) then

notEmpty:= true;

INC(i);

end;

if (notEmpty = true) then C[0]:= Y[0] // Если НОП не пуста, присваиваем ед. возможное значение

else C[0]:= -1; // Иначе - код ошибки

end

else begin // Начинается рассм. нетривиального случая

x_index:= M div 2; // Делим X напополам

SetLength (SUB_X, x_index);

SetLength (SUB_Y, N);

for i:= 0 to x_index - 1 do // Заполняем подматрицы

SUB_X[i]:= X[i];

for i:= 0 to N - 1 do

SUB_Y[i]:= Y[i];

LCS_LENGTH (x_index, N, SUB_X, SUB_Y, L1); // Вычисляем L1

SetLength (SUB_X, M - x_index); // Меняем длину «подмассива» X

last_i:= High (SUB_X); // Получаем индекс последнего эл-та SUB_X

for i:= 0 to last_i do // Заполняем подматрицы

SUB_X[i]:= X [M - i - 1];

for i:= 0 to N - 1 do

SUB_Y[i]:= Y [N - i - 1];

LCS_LENGTH (M - x_index, N, SUB_X, SUB_Y, L2); // Вычисляем L2

lcs_max:= 0;

for i:= 0 to N do // Находим Max (L1j + L2n-j)

if (lcs_max < L1 [i] + L2 [N - i]) then

lcs_max:= L1 [i] + L2 [N - i];

if (lcs_max = 0) then exit; // Если lcs пуста, выходим.

i:= 0;

Found:= false;

while ((Found = false) and (i <= N)) do // Находим y_index

begin

if (lcs_max = L1 [i] + L2 [N - i]) then

begin

y_index:= i;

Found:= true

end;

INC(i);

end;

SetLength (SUB_X, x_index);

SetLength (SUB_Y, y_index);

for i:= 0 to x_index - 1 do // Заполняем подматрицы

SUB_X[i]:= X[i];

for i:= 0 to y_index - 1 do

SUB_Y[i]:= Y[i];

SetLength (C1, lcs_max);

SetLength (C2, lcs_max);

j:= High(C1);

for i:= 0 to j do

begin

C1 [i]:= -1;

C2 [i]:= -1;

end;

LCS (x_index, y_index, SUB_X, SUB_Y, C1);

SetLength (SUB_X, M - x_index);

SetLength (SUB_Y, N - y_index);

last_i:= High (SUB_X);

for j:= 0 to last_i do // Заполняем подматрицы

SUB_X[j]:= X [x_index + j];

last_i:= High (SUB_Y);

for j:= 0 to last_i do

SUB_Y[j]:= Y [y_index + j];

LCS (M - x_index, N - y_index, SUB_X, SUB_Y, C2);

k:= 0;

j:= Length(C1);

while ((k < j) and (C1 [k] <> -1)) do // Объединяем С1 и С2 в С

begin

C[k]:= C1 [k];

INC(k);

end;

i:= k;

k:= 0;

j:= Length(C2);

while ((k < j) and (C2 [k] <> -1)) do

begin

C [i+k]:= C2 [k];

INC(k);

end;

end;

end;

// Заполнение матрицы расстояний

function EditDinst (D: IntMatrix; X: IntArray; Y: IntArray; i, j: longint): longint;

var

res, prev, m: longint;

begin

res:= D [1, j - 1] + 1;

prev:= D [0, j] + 1;

if (res > prev) then res:= prev;

if X [i - 1] = Y [j - 1] then m:= 0

else m:= 1;

prev:= D [0, j - 1] + m;

if (res > prev) then res:= prev;

EditDinst:= res;

end;

// Функция вычисляющая расстояние Левенштейна

function Levenshtein (X: IntArray; Y: IntArray; l1: longint; l2: longint): longint;

var i, j: longint;

D: IntMatrix;

begin

SetLength (D, 2);

SetLength (D[0], l2 + 1);

SetLength (D[1], l2 + 1);

for i:= 0 to l2 do // Заполняем первую строку

D [0, i]:= i;

for i:= 1 to l1 do

begin

D [1, 0]:= i; // Первый элемент в строке

for j:= 1 to l2 do

D [1, j]:= EditDinst (D, X, Y, i, j);

for j:= 0 to l2 do

D [0, j]:= D [1, j];

end;

Levenshtein:= D [1, l2];

end;

// Процедура, выводящая на печать результаты

// вычислений

procedure PrintLCS();

var i: longint;

begin

writeln ('Первая строка:');

for i:= 0 to Length1 - 1 do

write (S1 [i], ' ');

writeln();

writeln ('Вторая строка:');

for i:= 0 to Length2 - 1 do

write (S2 [i], ' ');

writeln();

writeln ('Наибольшая общая подпоследовательность: ');

i:= 0;

if (SEQ[0] = -1) then

writeln ('НОП пустая')

else

while ((i <= High(SEQ)) and (SEQ[i] <> -1)) do

begin

write (SEQ[i], ' ');

INC(i);

end;

end;

procedure PrintEditDinst();

begin

writeln();

write ('Редакционное расстояние: ', Levenshtein (S1, S2, Length1, Length2));

end;

// Процедура, осуществляющая вывод результатов в файл

//

procedure PrintLCSToFile();

var i: longint;

begin

assign (output, 'LCS.txt'); // Файл OUTPUT определен в System и указывает устройство вывода

// => просто и элегантно перенаправляем вывод в файл

rewrite(output); //

writeln ('Наибольшая общая подпоследовательность: ');

i:= 0;

if (SEQ[0] = -1) then

writeln ('НОП пустая')

else

while ((i <= High(SEQ)) and (SEQ[i] <> -1)) do

begin

writeln (SEQ[i]);

INC(i);

end;

close(output);

end;

procedure PrintEditDinstToFile();

begin

assign (output, 'EditDinst.txt');

rewrite(output);

write ('Редакционное расстояние: ', Levenshtein (S1, S2, Length1, Length2));

close(output);

end;

begin

assign (file1, 'EditDinst.txt');

erase(file1);

assign (file1, 'LCS.txt');

erase(file1);

assign (file1, 'Period.txt');

erase(file1);

mode:= -1;

writeln ('Выберите, что необходимо сделать (необходимо ввести число и нажать Enter): ');

writeln ('1. Наибольшая общая подпоследовательность');

writeln ('2. Редакционное расстояние');

writeln ('3. Наибольший период наибольшей кратности');

writeln ('4. Всё');

writeln ('0. Выход');

while((mode <> 1) and (mode <> 2) and (mode <> 3) and (mode <> 4) and (mode <> 0)) do

try

begin

write ('Ввод: ');

readln(mode);

end;

except

mode:= -1;

end;

try

begin

ReadFromFile (file1, 'S1.txt', S1);

if Length(S1) = 0 then

begin

writeln ('Файл S1.txt пуст');

exit;

end;

end;

except

begin

writeln ('Данные в файле S1.txt представлены в неверном формате.');

writeln ('Представьте данные в правильном формате и удалите пустые строки');

exit;

end;

end;

try

begin

ReadFromFile (file1, 'S2.txt', S2);

if Length(S2) = 0 then

begin

writeln ('Файл S2.txt пуст');

exit;

end;

end;

except

begin

writeln ('Данные в файле S2.txt представлены в неверном формате.');

writeln ('Представьте данные в правильном формате и удалите пустые строки');

exit;

end;

end;

InitSEQ(); // Инициализируется матрица и определяются Length1 и Length2

CASE mode of

0: begin

writeln ('Работа программы прервана пользователем');

exit;

end;

1: begin

writeln ('Результаты будут помещены в файл LCS.txt');

writeln ('Дождитесь окончания работы программы…');

LCS (Length1, Length2, S1, S2, SEQ);

PrintLCSToFile();

end;

2: begin

writeln ('Результаты будут помещены в файл EditDinst.txt');

writeln ('Дождитесь окончания работы программы…');

PrintEditDinstToFile();

end;

3: begin

writeln ('В какой строке искать период? (введите число и нажмите Enter)');

writeln ('1. Первая строка');

writeln ('2. Строка');

write ('Ввод: ');

while ((strNum <> 1) and (strNum <> 2)) do

try

readln(strNum);

except

strNum:= 0;

end;

writeln ('Результаты будут помещены в файл Period.txt');

writeln ('Дождитесь окончания работы программы…');

if (strNum = 1) then

FindMaxPeriod(S1)

else

FindMaxPeriod(S2);

end;

4: begin

writeln ('В какой строке искать период? (введите число и нажмите Enter)');

writeln ('1. Первая строка');

writeln ('2. Строка');

write ('Ввод: ');

while ((strNum <> 1) and (strNum <> 2)) do

try

readln(strNum);

except

strNum:= 0;

end;

writeln ('Результаты будут помещены в файлы LCS.txt, EditDinst.txt и Period.txt');

writeln ('Дождитесь окончания работы программы…');

if (strNum = 1) then

FindMaxPeriod(S1)

else

FindMaxPeriod(S2);

LCS (Length1, Length2, S1, S2, SEQ);

PrintLCSToFile();

PrintEditDinstToFile();

end;

end;

try

close(Output);

except

end;

writeln ('Работа программы окончена.');

end.

Код основной программы на языке C

#include <stdio.h>

#include <stdbool.h>

#include <stdlib.h>

// Вычисление минимального значения

int Min (int X, int Y)

{

if (X < Y)

return X;

else

return Y;

}

// Вычисление максимального значения

int Max (int X, int Y)

{

if (X > Y)

return X;

else

return Y;

}

// Поиск подстроки в строке

long int subString (int str[], long int strSize, int subStr[], long int subStrSize, long int firstIndex)

{

_Bool isFind;

int lastIndex = strSize - subStrSize;

if (firstIndex <= lastIndex) {

for (long int i = firstIndex; i <= lastIndex; i++)

{

isFind = true;

for (long int j = 0; j < subStrSize; j++)

if (subStr[j]!= str [i + j])

isFind = false;

if (isFind == true) return i;

}

}

return -1;

}

// Процедура, вычисляющая вектор, равный последней строке матрицы НОП

int * lcsLength (long int m, long int n, int X[], int Y[], int LL[]) {

long int **H = (long int **) malloc (2 * sizeof (long int *));

long int i = 0, j = 0;

for (i = 0; i < 2; i++)

H[i] = (long int *) malloc((n + 1) * sizeof (long int));

for (i = 0; i <= n; i++) // Инициализируем вторую строку

H[1] [i] = 0;

for (i = 0; i < m; i++) // Вычисляем Н

{

for (j = 0; j <= n; j++) // Сдвигаем вторую строку вверх

H[0] [j] = H[1] [j];

for (j = 0; j < n; j++)

{

if (X[i] == Y[j])

H[1] [j + 1] = H[0] [j] + 1;

else

{

if (H[1] [j] > H[0] [j + 1])

H[1] [j + 1] = H[1] [j];

else

H[1] [j + 1] = H[0] [j + 1];

}

}

}

for (j = 0; j <= n; j++)

LL[j] = H[1] [j];

for (i = 0; i < 2; i++) // Освобождаем память

free (H[i]);

free(H);

H = NULL;

return LL;

}

// Вычисление LCS

int * lcs (long int m, long int n, int X[], int Y[], int C[]) {

long int i = 0, j = 0; // Инициализация для цикла While

int *L1 = (int *) malloc((n + 1) * sizeof(int));

int *L2 = (int *) malloc((n + 1) * sizeof(int));

for (i = 0; i <= n; i++)

{

L1 [i] = 0;

L2 [i] = 0;

}

_Bool notEmpty = false;

if ((m == 0) | (n == 0)) // Тривиальный случай

{

C[0] = -1;

return C;

}

else if (m == 1)

{

i = 0;

while ((notEmpty!= true) & (i < n))

{

if (X[0] == Y[i])

notEmpty = true;

i++;

}

if (notEmpty == true) // Если НОП не пуста, присваиваем ед. возможное значение

C[0] = X[0];

else

C[0] = -1; // Иначе - код ошибки

//C = NULL;

return C;

}

else if (n == 1)

{

i = 0;

while ((notEmpty!= true) & (i < m))

{

if (Y[0] == X[i])

notEmpty = true;

i++;

}

if (notEmpty == true) // Если НОП не пуста, присваиваем ед. возможное значение

C[0] = Y[0];

else

C[0] = -1; // Иначе - код ошибки

//C = NULL;

return C;

}

else // Начинается рассм. нетривиального случая

{

long int x_index = m / 2; // делим X напополам

int *SUB_X = (int *) malloc((x_index)* sizeof(int));

int *SUB_Y = (int *) malloc((n)* sizeof(int));

for (i = 0; i < x_index; i++) // заполняем подматрицы

SUB_X[i] = X[i];

for (i = 0; i < n; i++)

SUB_Y[i] = Y[i];

L1 = lcsLength (x_index, n, SUB_X, SUB_Y, L1); // Вычисяем L1

free (SUB_X);

free (SUB_Y);

SUB_X = (int *) malloc((m - x_index)* sizeof(int));

SUB_Y = (int *) malloc((n)* sizeof(int));

long int last_i = m - x_index;

for (i = 0; i < last_i; i++) // заполняем подматрицы

SUB_X[i] = X [m - i - 1];

for (i = 0; i < n; i++)

SUB_Y[i] = Y [n - i - 1];

L2 = lcsLength (m - x_index, n, SUB_X, SUB_Y, L2); // Вычисляем L2

long int lcs_max = 0;

for (i = 0; i <= n; i++)

lcs_max = Max (lcs_max, L1 [i] + L2 [n - i]);

if (lcs_max == 0) return C; // Если lcs пуста, выходим.

i = 0;

_Bool found = false;

long int y_index;

while ((found == false) & (i <= n)) // находим y_index

{

if (lcs_max == L1 [i] + L2 [n - i])

{

y_index = i;

found = true;

}

i++;

}

free (SUB_X); // Освобождаем память

free (SUB_Y);

free(L1);

free(L2);

SUB_X = (int *) malloc((x_index)* sizeof(int));

SUB_Y = (int *) malloc((y_index)* sizeof(int));

for (i = 0; i < x_index; i++) // Заполняем матрицы

SUB_X[i] = X[i];

for (i = 0; i < y_index; i++)

SUB_Y[i] = Y[i];

int *C1 = (int *) malloc((lcs_max + 1)* sizeof(int));

int *C2 = (int *) malloc((lcs_max + 1)* sizeof(int));

for (i = 0; i <= lcs_max; i++)

{

C1 [i] = -1;

C2 [i] = -1;

}

C1 = lcs (x_index, y_index, SUB_X, SUB_Y, C1);

free (SUB_X); // Освобождаем память

free (SUB_Y);

SUB_X = (int *) malloc((m - x_index)* sizeof(int));

SUB_Y = (int *) malloc((n - y_index)* sizeof(int));

last_i = m - x_index;

for (j = 0; j < last_i; j++)

SUB_X[j] = X [x_index + j];

last_i = n - y_index;

for (j = 0; j < last_i; j++)

SUB_Y[j] = Y [y_index + j];

C2 = lcs (m - x_index, n - y_index, SUB_X, SUB_Y, C2);

long int k = 0;

while ((k < m - x_index) && (C1 [k]!= -1))

{

C[k] = C1 [k];

k++;

}

long int k_1 = k;

k = 0;

while ((k < n - y_index) && (C2 [k]!= -1))

{

C [k_1 + k] = C2 [k];

k++;

}

//C [k_1 + k] = -1;

free(C1); // не забываем освобождать память

free(C2);

free (SUB_X);

free (SUB_Y);

return C;

}

}

// Заполнение матрицы расстояний

long int editDinst (long int D[], long int n, int X[], int Y[], long int i, long int j) {

int m;

long int res = D [1 * n + j - 1] + 1;

long int prev = D [0 * n + j] + 1;

if (res > prev)

res = prev;

if (X [i - 1] == Y [j - 1])

m = 0;

else m = 1;

prev = D [0 * n + j - 1] + m;

if (res > prev)

res = prev;

return res;

}

// Вычисление расстояния Левенштейна

long int levenshtein (int X[], int Y[], long int l1, long int l2) {

long int i = 0, j = 0;

long int *D = (long int *) malloc (2 * (l2 + 1) * sizeof (long int));

for (i = 0; i <= l2; i++)

D[i] = i;

for (i = 1; i <= l1; i++)

{

D [1 * (l2 + 1)] = i;

for (j = 1; j <= l2; j++)

D [1 * (l2 + 1) + j] = editDinst (D, l2, X, Y, i, j);

for (j = 0; j <= l2; j++)

D [0 * (l2 + 1) + j] = D [1 * (l2 + 1) + j];

}

long int res = D [1 * (l2 + 1) + l2];

free(D); // освобождаем память

D = NULL;

return res;

}

// Вычисление максимального периода

void findMaxPeriod (int str[], long int length) {

long int periodLength = length / 2;

long int maxMult = 1;

long int i = 0, j = 0;

long int index;

long int prev_index;

long int currMult;

long int offset;

long int size;

int *subStr = NULL;

long int *maxCurrMult = NULL;

while (periodLength > 0) // Начинаем с подстрок большей длины. Если находим период с кратностью >1, то закончили

{

size = ((length - (2 * periodLength)) + 1) * periodLength;

subStr = (int *) malloc (size * sizeof(int));

for (i = 0; i < size; i++)

subStr[i] = -1;

maxCurrMult = (long int *) malloc (length * sizeof (long int));

offset = 0;

while ((length - (offset + 2 * (periodLength)) + 1) > 0)

{

index = 0;

currMult = 1;

maxCurrMult[offset] = 1;

for (i = 0; i < periodLength; i++)

subStr [periodLength * offset + i] = str [i + offset];

prev_index = subString (str, length, &subStr [periodLength * offset], periodLength, 0);

while (index!= -1)

{

index = subString (str, length, &subStr [periodLength * offset], periodLength, prev_index + 1);

if (index == prev_index + periodLength) {

currMult++;

if (currMult > maxCurrMult[offset])

maxCurrMult[offset] = currMult;

}

else

currMult = 1;

prev_index = index;

}

if (maxCurrMult[offset] > maxMult)

maxMult = maxCurrMult[offset];

offset++;

}

if (maxMult > 1)

break;

if (periodLength > 1) {

free(subStr);

free(maxCurrMult);

}

subStr = NULL;

maxCurrMult = NULL;

periodLength -;

}

FILE *file;

if ((file = fopen («Period.txt», «w»))!= NULL) {

if ((maxMult < 2) || (subStr == NULL))

fprintf (file, «There is no periods of multiplicity 2 in the initial string\n»);

else

{

fprintf (file, «Maximum period:%d\n», periodLength);

fprintf (file, «Multiplicity:%d\n», maxMult);

j = 0;

_Bool alreadyWas;

long int offset;

for (offset = 0; offset < size; offset++)

{

alreadyWas = false;

if (maxCurrMult[offset] == maxMult)

{

for (i = 0; i < offset; i++)

if (subString (&subStr[i * length], periodLength, &subStr [offset * length], periodLength, 0)!= -1)

alreadyWas = true;

if (alreadyWas) continue;

j++;

fprintf (file, «Period #%d:\n», j);

for (i = 0; i < periodLength; i++)

fprintf (file, «%d», subStr [offset * periodLength + i]);

fprintf (file, «\n»);

}

}

}

fclose(file);

}

free(subStr);

free(maxCurrMult);

subStr = NULL;

maxCurrMult = NULL;

}

void printLCSToFile (int C[]) {

long int i;

FILE *file1;

if ((file1 = fopen («LCS.txt», «w»))!= NULL) {

fprintf (file1, «LCS:\n»);

i = 0;

while (C[i] > 0)

{

fprintf (file1, «%d\n», C[i]);

i++;

}

fclose(file1);

}

}

void printEDToFile (long int editDinstance) {

FILE *file;

if ((file = fopen («EditDinst.txt», «w»))!= NULL) {

fprintf (file, «EditDinst:%d», editDinstance);

fclose(file);

}

}

int main() {

long int i;

int A = -1, B = -1;

FILE *file1;

long int length1 = 0;

long int length2 = 0;

int *S1;

int *S2;

char strNum;

remove («LCS.txt»);

remove («EditDinst.txt»);

remove («Period.txt»);

// Читаем из первого файла

if ((file1 = fopen («S1.txt», «r»)) == NULL) {

printf («File \ «S1.txt\» not Exist\n»);

return EXIT_FAILURE;

}

else

{

while (fscanf (file1, «%d % d», &A, &B)!= EOF)

{

if ((A < 0) || (B < 0))

{

printf («Data in file \ «S1.txt\» is incorrect\n»);

return EXIT_FAILURE;

}

length1++;

}

if (length1 == 0) {

printf («File \ «S1.txt\» is empty\n»);

return EXIT_FAILURE;

}

S1 = (int *) malloc (length1 * sizeof(int));

i = 0;

fclose(file1);

file1 = fopen («S1.txt», «r»);

while (fscanf (file1, «%d % d», &A, &B)!= EOF) {

S1 [i] = A;

i++;

}

fclose(file1);

}

// Читаем из второго файла

A = -1, B = -1;

if ((file1 = fopen («S2.txt», «r»)) == NULL) {

printf («File \ «S2.txt\» not Exist\n»);

return EXIT_FAILURE;

}

else

{

while (fscanf (file1, «%d % d», &A, &B)!= EOF)

{

if ((A < 0) || (B < 0))

{

printf («Data in file \ «S2.txt\» is incorrect\n»);

return EXIT_FAILURE;

}

length2++;

}

if (length2 == 0) {

printf («File \ «S2.txt\» is empty\n»);

return EXIT_FAILURE;

}

S2 = (int *) malloc (length2 * sizeof(int));

i = 0;

fclose(file1);

file1 = fopen («S2.txt», «r»);

while (fscanf (file1, «%d % d», &A, &B)!= EOF) {

S2 [i] = A;

i++;

}

fclose(file1);

}

long int editDinstance;

long int size = Max (length1, length2);

int *C = (int *) malloc (size * sizeof(int));

for (int i = 0; i < size; i++)

C[i] = -1;

printf («Choose what need to do (input the number and press Enter):\n»);

printf («1. Largest common subsequence\n»);

printf («2. Edit dinstance (Levenshtein)\n»);

printf («3. The largest period of the largest multiplicity\n»);

printf («4. All\n»);

printf («0. Exit\n»);

char choice;

char err;

do

{

printf («Input:»);

choice = getchar();

if ((err = getchar())!= '\n') choice = '9';

fflush(stdin);

} while (! strchr («12340», choice));

switch (choice)

{

case '0':

printf («Program aborted by user.\n»);

return EXIT_FAILURE;

break;

case '1':

printf («The results will be placed in file \ «LCS.txt\"\n»);

printf («Please, wait until the end of work.\n»);

C = lcs (length1, length2, S1, S2, C);

printLCSToFile(C);

break;

case '2':

printf («The results will be placed in file \ «EditDinst.txt\"\n»);

printf («Please, wait until the end of work.\n»);

editDinstance = levenshtein (S1, S2, length1, length2);

printEDToFile(editDinstance);

break;

case '3':

printf («Choose string to find period\n»);

printf («1. First string\n»);

printf («2. Second string\n»);

do

{

printf («Input:»);

strNum = getchar();

if ((err = getchar())!= '\n') choice = '9';

fflush(stdin);

} while (! strchr («12», strNum));

printf («The results will be placed in file \ «Period.txt\"\n»);

printf («Please, wait until the end of work.\n»);

if (strNum == '1')

findMaxPeriod (S1, length1);

else

findMaxPeriod (S2, length2);

break;

case '4':

printf («Choose string to find period\n»);

printf («1. First string\n»);

printf («2. Second string\n»);

do

{

printf («Input:»);

strNum = getchar();

if ((err = getchar())!= '\n') choice = '9';

fflush(stdin);

} while (! strchr («12», strNum));

printf («The results will be placed in files \ «LCS.txt\», \ «EditDinst.txt\» and \ «Period.txt\"\n»);

printf («Please, wait until the end of work.\n»);

if (strNum == '1')

findMaxPeriod (S1, length1);

else

findMaxPeriod (S2, length2);

C = lcs (length1, length2, S1, S2, C);

printLCSToFile(C);

editDinstance = levenshtein (S1, S2, length1, length2);

printEDToFile(editDinstance);

break;

default:

break;

}

printf («Program is complete successfully.\n»);

free(C);

free(S1);

free(S2);

return 0;

}

Код программы, генерирующей строки с заданными характеристиками

var

strLength, periodLength, periodMult, generated:longint;

offset, globalIndex, i, j, differs, changeIndex: longint;

period, str, changesIndexes: array of integer;

alreadyWas: boolean;

file1: text;

begin

strLength:= 0;

writeln ('Генерация первой последовательности');

repeat

write ('Длина периода: ');

readln(periodLength);

until (periodLength > -1);

if (periodLength > 0) then

begin

repeat

write ('Кратность периода: ');

readln(periodMult);

until (periodMult > 0);

repeat

write ('Смещение начало периода относительно начала строки: ');

readln(offset);

until (offset > -1);

end

else

begin

periodMult:= 0;

offset:= 0;

end;

repeat

write ('Длина строки: ');

readln(strLength);

if ((offset + periodLength * periodMult) > strLength) then

writeln ('Указанная длина строки меньше, чем (Смещение + Длина периода * Кратность) = ', offset + periodLength * periodMult)

until (offset + periodLength * periodMult <= strLength);

if (strLength < 1) then

begin

writeln ('Введенные параметры соответствуют пустой строке, генерация прервана.');

EXIT;

end;

setLength (period, periodLength);

setLength (str, strLength);

randomize;

for i:= 0 to periodLength - 1 do

period[i]:= random(1000);

globalIndex:= 0;

while (globalIndex < offset) do

begin

str[globalIndex]:= random(1000);

inc(globalIndex);

end;

for j:= 1 to periodMult do

for i:= 0 to periodLength - 1 do

begin

str[globalIndex]:= period[i];

inc(globalIndex);

end;

while (globalIndex < strLength) do

begin

str[globalIndex]:= random(1000);

inc(globalIndex);

end;

assign (output, 'S1.txt');

rewrite(output);

for i:= 0 to strLength - 2 do

writeln (str[i], ' ', i);

write (str[strLength - 1], ' ', strLength - 1);

close(output);

writeln ('Сгенерированная строка помещена в файл «S1.txt» ');

writeln();

writeln ('Генерация второй последовательности');

write ('Введите количество отличий второй строки от первой: ');

readln(differs);

setLength (changesIndexes, strLength);

for i:= 0 to strLength - 1 do

changesIndexes[i]:= 0;

i:= 0;

while (i < differs) do

begin

alreadyWas:= false;

changeIndex:= random (strLength - 1);

if (changesIndexes[changeIndex] = 0) then

begin

generated:= random(1000);

repeat

if (generated <> str[changeIndex]) then

str[changeIndex]:= random(1000);

until (generated <> str[changeIndex]);

inc(i);

end

else

changesIndexes[changeIndex]:= 1;

end;

assign (output, 'S2.txt');

rewrite(output);

for i:= 0 to strLength - 2 do

writeln (str[i], ' ', i);

write (str[strLength - 1], ' ', strLength - 1);

close(output);

writeln ('Сгенерированная строка помещена в файл «S2.txt» ');

end

Размещено на Allbest.ru