Начало
Соревнования
8. Новое слово в рекламе
Сложная задача на работу со строками.
Будем перебирать все возможные K от 1 до |s|, пока набор из K блоков, содержащих заданное слово s, не будет найден.
Назовем K-подсловом wj, где j от 1 до K, последовательность букв из s вида sj sK+j s2K+j ….
Для каждого K заполняем массив T[1..L, 1..K] следующим образом. Вначале массив инициализируется нулями. Затем устанавливаем T[i,j]=m, если K-подслово wj начинается с позиции i в блоке Bm. Заполнения массива 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).
