Начало
Соревнования
8. Новое слово в рекламе
Сложная задача на работу со строками.
Будем перебирать все возможные `K` от 1 до `|s|`, пока набор из `K` блоков, содержащих заданное слово `s`, не будет найден.
Назовем `K`-подсловом `w_j`, где `j` от 1 до `K`, последовательность букв из `s` вида `s_j\ s_{K+j}\ s_{2K+j}\ …`.
Для каждого `K` заполняем массив `T`[1..`L`, 1..`K`] следующим образом. Вначале массив инициализируется нулями. Затем устанавливаем `T`[`i,j`]=`m`, если `K`-подслово `w_j` начинается с позиции `i` в блоке `B_m`. Заполнения массива `T` выполняется за время `O(K*N*L*|s|/K)=O(|s|*N*L)`.
var s:string;
b:array[1..100] of string; { блоки }
T:array[1..100,1..200] of integer;
n,L,i,j,k,m,p,q,wlen,slen:integer;
flg:boolean;
...
slen:=length(s);
for k:=1 to length(s) do
begin
{ заполнение таблицы T }
for i:=1 to L do
for j:=1 to k do
T[i,j]:=0;
for j:=1 to k do
begin
wlen:=(slen-j+k) div k; { длина j-го K-подслова }
for i:=1 to L-wlen+1 do
for m:=1 to n do
begin
{ проверяем, что j-е K-подслово начинается с позиции i в блоке m }
p:=j;
q:=i;
while (p<=slen) and (b[m][q]=s[p]) do
begin
inc(q);
p:=p+k;
end;
if p>slen then
begin
T[i,j]:=m;
break;
end;
end;
end;
...
end;
writeln(-1);
После этого мы должны найти в этом массиве последовательность из `K` ненулевых ячеек, начиная с некоторой ячейки `(i,j)`: `T`[`i,j`] `T`[`i,j+1`] … `T`[`i,K`] `T`[`i-1,1`] … `T`[`i-1,j-1`]. Номера блоков в этих ячейках образуют требуемый набор блоков. Поиск последовательности из `K` ненулевых ячеек в массиве `T` можно выполнить за время `O(L*K)`, если при обнаружении нулевой ячейки сдвигаться на `K` позиций от нее.
i:=1;
j:=1;
while i<=L do
begin
flg:=true;
for p:=j to k do
if T[i,p]=0 then
begin
flg:=false;
i:=i+1;
j:=p;
break;
end;
if flg then
for p:=1 to j-1 do
if T[i-1,p]=0 then
begin
flg:=false;
j:=p;
break;
end;
if flg then
begin
{ вывод ответа }
writeln(k);
for p:=j to k do
write(' ',T[i,p]);
for p:=1 to j-1 do
write(' ',T[i-1,p]);
writeln;
halt(0);
end;
end;
Общее время работы алгоритма равно `O(|s|*(|s|*N*L+K*L))=O(|s|^2*N*L)`.
