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

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

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

Пример.

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

Решение

Program F1;

constk=255;

input='input.txt';

output='output.txt';

varx: array[1..k] ofinteger;

m,n,j: integer;

s1,s2,s: string;

f:text;

label1;

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

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

functionposl(m:integer):boolean;

varj,f:integer;

label10,20;

Begin

f:=0;

posl:=true;

forj:=m downto1 do

ifx[j]=n+j-m thenf:=j

Else

Begin

inc(x[j]);

goto10

end;

10: iff<>0 then iff=1 then

Begin

posl:=false;

goto20

End

else forj:=f tom dox[j]:=x[f-1]+j-f+1;

20:

end;

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

procedureprints(m:integer);

vari:integer;

z:string;

Begin

write(m,': ');

fori:=1 tom do

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

writeln(z);

assign(f,output);

rewrite(f);

write(f,z);

close(f);

readln;

end;

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

functionspc(s:string):string;

varstr:string;

i:integer;

Begin

str:='';

fori:=1 tolength(s) do

ifs[i]<>' ' thenstr:=str+s[i];

spc:=str;

end;

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

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

functionequal(m:integer):boolean;

vari,j:integer;

Begin

j:=1;

fori:=1 tolength(s2) do

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

ifj>m thenequal:=true elseequal:=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 begins:=s1; s1:=s2; s2:=s end;

n:=length(s1);

form:=n downto1 do

Begin

forj:=1 tom dox[j]:=j;

Repeat

ifequal(m) then

Begin

prints(m);

goto1;

end;

until notposl(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.

Наши рекомендации