Рекуррентные соотношения Опции

[passat]

Даны две строки символов. Длина строки указана.
Первую строку можно менять циклически (т.е. перставлять начальный символ в конец строки).

Выяснить, можно ли получить вторую строку из первой путем циклической перестановки и, если можно, указать количество перестановок.

Придумал 2 алгоритма:
1) Поиск последовательности символов второй строки в первой. Но не осилил рекуррентное соотношение.
2) Собственно перестановка с проверкой строки целиком. Тут вообще нет рекуррентного соотношения. Да и выполняться будет наверное медленно.

Может кто подскажет более интересный способ. Желательно с рекуррентной формулой.

[klem4]

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

{$mode tp}
{$b-}
uses crt;

function foo( s, pattern: string ): integer;
var
  i, j, start: byte;
  changes: integer;

begin
  if length(s) <> length(pattern) then exit(-1);
  i := 1;
  changes := -1;
  while ( i <= length(s) ) and ( changes = -1 ) do begin
    while ( i <= length(s) ) and ( s[i] <> pattern[1] ) do inc(i);
    if i <= length(s) then begin
      j := 2;
      start := i;
      inc(i);
      if ( i > length(s) ) then i := 1;
      while ( s[i] = pattern[j] )
        and ( j <= length(pattern) )
        and ( i <> start ) do begin
          inc(j);
          if ( i < length(s) ) then inc(i) else i := 1;
      end;
      if j > length( pattern ) then changes := start-1 else i := start + 1;
    end;
  end;
  foo := changes;
end;

var
  a, b: string;
begin
  clrscr;
  a := 'abcd';
  b := 'dabc';
  writeln( foo( a, b) );
end.

[volvo]

Андрей, вот так не проще?

function check(s, patt: string): integer;
begin
  if length(s) <> length(patt) then check := -1
  else check := pos(patt, s + s) - 1;
end;

var
  s, patt: string;

begin
  s := 'abcd';
  patt := 'bcda';
  writeln(check(s, patt));
end.

Только рекуррентностью тут и не пахнет... При длине строки > 127 начнутся проблемы при использовании компилятора TP...

[klem4]

Хах))) Щас чуть такое же решение не запостил))) Да, на счет строк больше 127 тут засада.

Сообщение отредактировано: klem4 - 21.02.2009 14:49