Наибольшая общая часть строк. Опции

[Гость]

Помогите пожалуйста выполнить задачу.
Есть две строки надо выделить наибольшую общую часть из них.
Я вообще не понял чего это значит?


внимательнее с названием темы!

Сообщение отредактировано: Oleg_Z - 23.06.2005 18:34

[VBproffi]

Никаких топиков вида "Помогите!!!!" или "Горю!Сделайте курсовую!!".Эти темы закрываются и удаляются.

(короче все не информативные названия) :nono: ;)

Нодо просомотреть какие значения из второй строки есть в первой и выписать их.

Код

Uses
    CRT;
var
    count    : Byte;
    StrIn,
    StrOut   : String[30];
    FileIn,
    FileOut  : Text;
    ItS, pob : String[30]
begin
    ClrScr;
            Assign(FileIn, 'C:/FileIn.txt');
            Assign(FileOut, 'C:/FileOut.txt');

             Reset(FileIn);
             ReWrite(FileOut);

             ReadLn(FileIn,StrIn);
             Read(FileIn, StrOut);

             For count:= 1 to Length(StrOut) do
                  begin
                       pob:= Copy(StrOut,count,1);
                       If Pos(pob,StrIn) > 0 then
                          ItS:=ItS+pob;
                  end;


             WriteLn(FileOut, ItS);
            Close(FileOut);
            Close(FileIn);
    ReadKey;
end.

Сообщение отредактировано: VBproffi - 23.06.2005 10:52

[klem4]

помоему это решается так :

uses
    crt;
var
    s1,s2:string;

function GetMaxStr(var ss1,ss2:string):string;
var
    MaxS,Chek:string;
    i,right,left:integer;

begin

   MaxS:='';

   // ss1 - меньшая

   i:=1;

   repeat

      left:=i;

      right:=length(ss1);

      repeat


         Chek:=copy(ss1,left,right-left+1);


         if (pos(Chek,ss2)>0)and(Length(Chek)>Length(MaxS)) then
          MaxS:=Chek;

         dec(right);


      until(right-left<length(MaxS));

      inc(i);

   until (i>length(ss1));


   GetMaxStr:=MaxS;

End;




Begin

   clrscr;

   write('s1 = '); readln(s1);
   write('s2 = '); readln(s2);

   writeln;

   write('Результат : ');

   if length(s1)<length(s2) then
    writeln(GetMaxStr(s1,s2))
   else writeln(GetMaxStr(s2,s1));

   readln;

End.

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

Сообщение отредактировано: klem4 - 28.06.2005 20:25

[volvo]

Вообще-то это задача на динамическое программирование: LCS - Largest Common Sequence. Вот тут было решение, если кому интересно: http://www.sumdu.edu.ua/tournament/mathema.../simple/inform/

[klem4]

Вот это не подойдет ?

Лучше одним постом выше - алгоритм Нудельмана, это то, что нужно...

Сообщение отредактировал volvo - Сегодня, 06:26 PM

Согласен :D
Сообщение отредактировал klem4 - Сегодня, 07:45 PM

Клем, сообщение отрадактирвоанно пишется мелким шрифтом иначе не правдоподобно!

Сообщение отредактировано: Oleg_Z - 28.06.2005 22:55

[virt]

а по клемовской ссылке тоже алгоритм нудельмана.

к тому же он выдает все подстроки максимальной длины ,а по ссылке volvo только одну.

virt, я имел в виду на 1 пост выше того, КУДА ведет ссылка klem4, на то, что ты и выкладывал ;) Просто при редактировании klem4 зачем-то удалил мою ссылку ...

Сообщение отредактировано: volvo - 28.06.2005 23:10