Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TA_last_u3.doc
Скачиваний:
2
Добавлен:
01.04.2025
Размер:
3 Мб
Скачать
☆

Перший варіант розв’язку

Досить простий шлях з точки зору теоретичної підготовки та реалізації програми – це аналог пошуку найменшого елементу в масиві. Тобто ми розглядаємо наші зсуви як незалежні l стрічок, для пошуку найменшої з яких ми робимо l‑1=O(l) порівнянь поточної найменшої з поточною, що розглялається.

Коректність алгоритму не викликає сумнівів, хоча її можна строго довести індукцією за кількістю розглянутих стрічок.

Алгоритм при вдалому методі зберігання даних використовує O(l) пам’яті, причому крім вхідної стрічки займається лише O(1) пам’яті.

А от з часом буде гірше. Коли стрічки мало схожі одна на одну (наприклад, мають різні початки), то l порівнянь займає O(l) часу. Але якщо стрічки схожі (наприклад, вхідна стрічка має досить короткий період), то часу на порівняння буде використовуватись уже O(l2) – по O(l) на O(l) порівнянь.

Ось програма на Паскалі, яка реалізує вищеописаний алгоритм.

(Програма читає дані з файлу b.in, в якому перша цифра – кількість тестів, а кожний тест містить цифру – кількість символів у стрічці, а за нею саму стрічку. Результати у порядку, відповідному до порядку тестів, віводяться на екран.)

PROGRAM Minlex1;

var c0:array[0..62499] of byte;{Given string.}

t,u:longint;{Number of all tests and of current test.}

l:longint;{Length of the string.}

i,i1,i2:longint;{Indices for cycles.}

ch0:char; {Char, which is used for reading the data.}

idend:byte; {Indicator of the end of the cycle.}

{Gets the order of i-th char of the (2l-1)-char string,

which has our l-char string as a period.}

FUNCTION c(i:longint):byte;

var k:longint;

j:word;

d:byte;

Begin

if (i>=l) then i:=i-l;

c:=c0[i];

End;

BEGIN

assign(input,'b.in');

reset(input);

read(t);

{This cycles passes once per each test.}

for u:=1 to t do begin

{Getting the input data.}

read(l);

if (l<=0) then writeln(0);

if (l>0) then begin

read(ch0);

while (ch0 in [#10,#13,#32]) do read(ch0);

c0[0]:=ord(ch0);

for i:=1 to (l-1) do begin

read(ch0);

c0[i]:=ord(ch0);

end;

i1:=0;

for i2:=1 to (l-1) do begin

idend:=0;

i:=0;

while ((idend=0)and(i<l)) do begin

if (c(i2+i)<>c(i1+i)) then idend:=1;

if (idend=0) then Inc(i);

end;

if (idend=1) then

if (c(i2+i)<c(i1+i)) then i1:=i2;

end;

writeln(i1);

end;

end;

close(input);

END.

Другий варіант розв’язку.

Другий варіант виграє за часом в порівнянні з першим, оскільки він використовує взаємозв’язок між стрічками і цим відмітає багато завідомо непотрібних порівнянь.

Розв’язок даної задачі зводиться до знаходження найпершого з тих символів, з якого починається одна з лексикографічно найменших підстрічок довжини l у стрічці довжиною 2l‑1, яка має задану нам l‑символьну стрічку в якості періоду. Пошук потрібної l‑символьної підстрічки, тобто позиції, з якої вона починається, здійснюється за наступним принципом.

Спочатку шукається найменший символ у стрічці (лексикографічно найменша стрічка може починатися тілький з найменшого символа). Номер найпершого представника найменшого символа позначимо через i1 – він і буде першим кандидатом на роль початку шуканої підстрічки.

Після цього відбувається прохід (2l‑1)‑символьної стрічки де номер j поточного символа, що перевіряється, пробігає значення від i1+1 до 2l‑2. У процесі перевірки значення j може повертатися назад, але це порушує лінійності алгоритму. На кожному кроці може бути другий кандидат на роль початку шуканої стрічки – i2. При цьому виконується наступне. Коли i2 існує (у програмі це відповідає стану idi2=1) – то початок шуканої стрічки не може бути під номером, меншим за i2 та відмінним від i1. А коли коли i2 не існує (idi2=0) – то початок шуканої стрічки не може бути під номером, меншим за j та відмінним від i1.

Якщо i2 не існувало та j<l ми призначаємо i2=j, за умови, що j‑ий символ дорівнює i1‑ому. Після цієї перевіркив незалежності від її результату j збільшується на 1. Якщо ж було j≥l (та i2 не існувало), то ми закінчуємо пошук з висновком, що i1 – шуканий розв’язок.

Якщо i2 існувало, ми порівнюємо j‑ий символ з (j‑i2+i1)‑им, розглядаючи наступні варіанти. Якщо ці символи рівні, ми просто збільшуємо j на 1. Якщо j‑ий символ виявляється більшим, ми відміняємо i2 та збільшуємо j на 1. Якщо j‑ий символ виявляється меншим, ми призначаємо i1=i1+((j‑1‑i1) div (i2‑i1))(i2‑i1); якщо при цьому стало було i1≥l, то ми закінчуємо пошук з висновком, що шуканий розв’язок – i1(попереднє)+((l‑1‑i1(попереднє)) div (i2‑i1(попереднє)))(i2‑i1(поперенднє)), якщо ж i1<l – ми відміняємо i2 та покладаємо j=i1+1.

Якщо цикл не закінчився у зв’язку з попередніми умовами завершення пошуку, але стало j≥2l‑1, ми закінчуємо пошук з висновком, що i1 – шуканий розв’язок. У протилежному випадку ми повертаємось до перевірки поточного j‑го символа.

Для обгрунтування коректності алгоритму доводиться індукцією за номером кроку наступне твердження: відповіддю на поставлену задачу не може бути номер, який менший за i2 та не дорівнює i1. У доведенні використовується те, що стрічка, що починаєть з символу з номером i1 та закінчується (j‑1)‑м символом, має період (i2‑i1).

Як і попередній, цей алгоритм при вдалому методі зберігання даних використовує O(l) пам’яті, причому крім вхідної стрічки займається лише O(1) пам’яті.

Лінійність алгоритму за часом слідує хоча б з того, що після кожного циклу вираз (2i1+j) збільшується принаймні на 1, а його максимальне значення є O(l).

Ось програма на Паскалі, яка реалізує вищеописаний алгоритм.

(Формати вводу та втводу – такі самі, як і в першому випадку.)

PROGRAM Minlex2;

var c0:array[0..62499] of byte;{Given string.}

cmin:byte;{Minimal order of the char in the string.}

cj,c2:byte; {Multi-used orders of chars.}

t,u:longint;{Number of all tests and of current test.}

l:longint;{Length of the string.}

i,i0,i1,i2,j,d:longint; {Indices for cycles.}

ch0:char; {Char, which is used for reading the data.}

idend,idi2,idproc:byte; {Indicators of events:

1 if such event is present, 0 if else.}

{Gets the order of i-th char of the (2l-1)-char string,

which has our l-char string as a period.}

FUNCTION c(i:longint):byte;

var k:longint;

j:word;

d:byte;

Begin

if (i>=l) then i:=i-l;

c:=c0[i];

End;

BEGIN

assign(input,'b.in');

reset(input);

read(t);

{This cycles passes once per each test.}

for u:=1 to t do begin

{Getting the input data.}

read(l);

if (l<=0) then writeln(0);

if (l>0) then begin

read(ch0);

while (ch0 in [#10,#13,#32]) do read(ch0);

c0[0]:=ord(ch0);

for i:=1 to (l-1) do begin

read(ch0);

c0[i]:=ord(ch0);

end;

{Finding the minimal order of the char in the string.}

i1:=0;

cmin:=c(0);

for i:=1 to (l-1) do begin

c2:=c(i);

if (c2<cmin) then begin

i1:=i;

cmin:=c2;

end;

end;

idend:=0;

idi2:=0;

j:=i1+1;

{Main cycle, which finds the best first position.}

while (idend=0) do begin

if (j>l*2-2) then idend:=1;

if (idend=0) then begin

idproc:=0;

cj:=c(j);

if (idi2=0) then begin

idproc:=1;

if (j>l-1) then idend:=1;

if ((idend=0)and(cj=cmin)) then begin

i2:=j;

idi2:=1;

end;

end;

if ((idi2=1)and(idproc=0)) then begin

d:=i2-i1;

c2:=c(j-d);

if (cj<>c2) then idi2:=0;

if (cj<c2) then begin

i0:=i1+(j-1-i1)-(j-1-i1) mod d;

if (i0>=l) then begin

i0:=i1+(l-1-i1)-(l-1-i1) mod d;

idend:=1;

end;

i1:=i0;

j:=i1;

end;

end;

end;

Inc(j);

end;

writeln(i1);

end;

end;

close(input);

END.

Також цей алгоритм легко узагальнити для пошуку лексикографічно найменшої підстрічки довжини b у стрічці довжини a (звісно, за час, лінійний від a).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]