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

Входные данные. В первой строке входного файла INPUT.TXT содержится первая фраза, во второй строке содержится вторая фраза.

Выходные данные. В файл OUTPUT.TXT выводится найденная последовательность символов.

Пример.

INPUT.TXT	OUTPUT.TXT
ПРИШЛА ВЕСНА РАССТАЯЛ СНЕГ	РЛСН

Решение

Program F1;

const k=255;

input='input.txt';

output='output.txt';

 

var x: array [1..k] of integer;

m,n,j: integer;

s1,s2,s: string;

f:text;

label 1;

 

{функция, которая на основе очередного сочетания

получает следующее по порядку сочетание}

function posl(m:integer):boolean;

var j,f:integer;

label 10,20;

Begin

f:=0;

posl:=true;

for j:=m downto 1 do

if x[j]=n+j-m then f:=j

Else

Begin

inc(x[j]);

goto 10

end;

10: if f<>0 then if f=1 then

Begin

posl:=false;

goto 20

End

else for j:=f to m do x[j]:=x[f-1]+j-f+1;

20:

end;

 

{процедура вывода результата на экран и записи в файл}

procedure prints(m:integer);

var i:integer;

z:string;

Begin

write(m,': ');

for i:=1 to m do

z:=z+s1[x[i]];

writeln(z);

 

assign(f,output);

rewrite(f);

write(f,z);

close(f);

readln;

 

end;

 

 

{функция spc удаляет из переданной в неё строки пробелы.}

function spc(s:string):string;

var str:string;

 

i:integer;

Begin

str:='';

for i:=1 to length(s) do

if s[i]<>' ' then str:=str+s[i];

spc:=str;

end;

 

{функция equal проверяет, входит ли очередная последовательность,

составленная из символов одной строки в другую}

function equal(m:integer):boolean;

var i,j:integer;

Begin

j:=1;

for i:=1 to length(s2) do

if (s1[x[j]]=s2[i]) and (j<=m) then j:=j+1;

if j>m then equal:=true else equal:=false;

end;

 

{тело программы}

Begin

assign(f,input);

reset(f);

readln(f,s1);

read(f,s2);

close(f);

 

s1:=spc(s1); s2:=spc(s2);

if (length(s2)<length(s1)) then begin s:=s1; s1:=s2; s2:=s end;

n:=length(s1);

for m:=n downto 1 do

Begin

for j:=1 to m do x[j]:=j;

Repeat

if equal(m) then

Begin

prints(m);

goto 1;

end;

until not posl(m);

end;

1:

 

end.

 

В этой программе процедура prints печатает найденную последовательность символов и её длину, функция equal проверяет, входит ли очередная последовательность, составленная из символов одной строки в другую, функция spc удаляет из переданной в неё строки пробелы.
Работу полученной программы можно значительно ускорить, если добавить в неё часть, в которой перед началом перебора из обеих строк удалялись бы те символы, которые встречаются только в одной из них. (Например, заданные в условии строки после такого преобразования приняли бы вид: РЛАЕСНА и РАСАЛСНЕ).

 

Тема: Эффективные структуры данных.

 

Условие задачи: В преддверии начала 13-го чемпионата страны по футболу в 1-й лиге организаторы решили провести жеребьевку календаря. Секретарь федерации предоставил списки команд с учетом занятых мест в 12-м чемпионате, но для того, чтобы жеребьевка прошла непредвзято и корректно необходимы списки команд по алфавиту, независимо от их достижений в прошлом году. Составить программу, преобразующую турнирную таблицу 12-го чемпионата, состоящую из N команд, в алфавитный список.

 

INPUT. TXT	Реал Барселона Атлетико Депортиво Сельта Севилья Гранада Валенсия	Количество команд (N)   Названия команд
OUTPUT.TXT	Атлетико Барселона Валенсия Гранада Депортиво Реал Севилья Сельта

 

Решение:

Program olimp1;

var

x: array[1..32] of string;

y: string;

i, j, n: integer;

Fd, Fs: Text;

begin

assign(Fd, ‘D:\input.txt’);

reset(Fd);

assign(Fs, ‘D:\output.txt’);

rewrite(Fs);

readln(Fd, N);

for i:=1 to N do

begin

readln(Fd, x[i]);

end;

for i:=1 to n-1 do

for j:=i+1 to n do

if x[i]>x[j] then

begin

y:=x[i];

x[i]:=x[j];

x[j]:=y;

end;

for i:=1 to n do

writeln (Fs, i:2,’.’+x[i]);

end.

 

Тема: Эффективные структуры данных.

 

Условие задачи: В преддверии начала 13-го чемпионата страны по футболу в 1-й лиге организаторы решили провести жеребьевку календаря. Секретарь федерации предоставил списки команд с учетом занятых мест в 12-м чемпионате, но для того, чтобы жеребьевка прошла непредвзято и корректно необходимы списки команд по алфавиту, независимо от их достижений в прошлом году. Составить программу, преобразующую турнирную таблицу 12-го чемпионата, состоящую из N команд, в алфавитный список.

 

INPUT. TXT	Реал Барселона Атлетико Депортиво Сельта Севилья Гранада Валенсия	Количество команд (N)   Названия команд
OUTPUT.TXT	Атлетико Барселона Валенсия Гранада Депортиво Реал Севилья Сельта

 

Решение:

Program olimp1;

var

x: array[1..32] of string;

y: string;

i, j, n: integer;

Fd, Fs: Text;

begin

assign(Fd, ‘D:\input.txt’);

reset(Fd);

assign(Fs, ‘D:\output.txt’);

rewrite(Fs);

readln(Fd, N);

for i:=1 to N do

begin

readln(Fd, x[i]);

end;

for i:=1 to n-1 do

for j:=i+1 to n do

if x[i]>x[j] then

begin

y:=x[i];

x[i]:=x[j];

x[j]:=y;

end;

for i:=1 to n do

writeln (Fs, i:2,’.’+x[i]);

end.