Версия для печати темы

Автор: lopata 20.03.2010 19:58

Строка называется m-знаковой, если она содержит m различных знаков. Строки a, ab und abcbaac 3-знаковые, а строка abcd 4-знаковая.
Дана строка s и число m , так что 1 <= m <= Length(s).
Необходимо написать
FUNCTION MaxMChainLen(s: STRING, m: INTEGER): INTEGER;
которая вычисляет длину самой длинной m-знаковой строки, которая содержится в строке s.

Идея сама понятна. Начала с самого простого. Просто вычисляю самую первую m-знаковой подстроку, которая попадется. А потом, насколько понимаю, нужно делать по алгоритму Кнута-Морриса-Пратта.

Моя идея, что, начиная с первого знака строки s, я копирую этот каждый знак в строку subs. если новый знак строки s не содержиться в строке subs, то увеличиваю счетчик на единицу. и так до тех пор, пока счетчик не будет равен m. А потом просто вычисляю длину строки subs.

Походу я что-то там намутила с циклами.. Код компилируется, а ничего не выдается.
Гляньте, пожалуйста.

FUNCTION MaxMChainLen(s: STRING; m: INTEGER):INTEGER;
VAR
i,j, count: INTEGER;
subs : STRING;
BEGIN
count := 0;
subs := '';
WHILE (count <> m) DO BEGIN
      FOR i := 1 to Length(s) DO BEGIN
          IF ( i = 1) THEN BEGIN
             subs := s[i];
             count := count+1;
          END (* if *)
              ELSE BEGIN
                   FOR j := 1 to Length(subs) DO BEGIN
                       IF (s[i]<> subs[j]) THEN
                          count := count+1;
                   subs:= subs+s[i];
                   END; (* for *)
              END; (* else *)
       END; (* for *)
END;(* while *)
END; (* MaxMChainLen *)

Автор: Unconnected 20.03.2010 20:55

Мне кажется, тут можно обойтись без Кнута-Морриса-Пратта, только вот правильно ли я понял задание.. Вот почему строки a и ab являются трёхсимвольными? По-моему, одно- и двух символьными соответственно.

Автор: lopata 20.03.2010 21:31

ну можно и без него)
здесь не a и ab , а a, ab Запятая в этом примере тоже является символом

Автор: Unconnected 21.03.2010 1:10

Можно так:

const mn:set of char=[];
var s:string;
    i,j,m,ind,count:byte;
    sym:array [1..255] of byte;

begin
  writeln('Vvedite Stroku');
  readln(s);
  writeln('Vvedite M');
  readln(m);
  fillchar(sym,sizeof(byte)*length(s),0);ind:=0;
  for i:=1 to length(s) do begin
    if not(s[i] in mn) then begin
      inc(ind);
      for j:=1 to length(s) do if s[j]=s[i] then inc(sym[ind]);
    end;
    include(mn,s[i]);
  end;
  for i:=1 to ind-1 do begin
    if sym[i]>sym[i+1] then begin
      count:=sym[i+1];
      sym[i+1]:=sym[i];
      sym[i]:=count;
    end;
  end;
  count:=0;
  for i:=1 to m do begin
    inc(count,sym[ind]);
    dec(ind);
  end;
  writeln('Maxlength=',count);
  readln;
end.

Автор: lopata 21.03.2010 1:16

насколько я понимаю, const mn:set of char=[]; это множество. А на учебе мы множества на паскале вообще никогда не применяли...

Добавлено через 2 мин.
поэтому этот код для меня загадка

Автор: Unconnected 21.03.2010 1:25

Тогда так:

var s:string;
    i,j,m,ind,mnind,count:byte;
    sym:array [1..255] of byte;
    mn:array[1..255] of char;

function check(c:char):boolean;
var u:byte;
begin
  check:=false;
  for u:=1 to mnind do if c=mn[u] then begin
                         check:=true;
                         break;
                       end;
end;

begin
  writeln('Vvedite Stroku');
  readln(s);
  writeln('Vvedite M');
  readln(m);
  fillchar(sym,sizeof(byte)*length(s),0);
  fillchar(mn,sizeof(char)*length(s),#0);
  ind:=0;mnind:=0;
  for i:=1 to length(s) do begin
    if not(check(s[i])) then begin
      inc(ind);inc(mnind);
      for j:=1 to length(s) do if s[j]=s[i] then inc(sym[ind]);
    end;
    mn[mnind]:=s[i];
  end;
  for i:=1 to ind-1 do begin
    if sym[i]>sym[i+1] then begin
      count:=sym[i+1];
      sym[i+1]:=sym[i];
      sym[i]:=count;
    end;
  end;
  count:=0;
  for i:=1 to m do begin
    inc(count,sym[ind]);
    dec(ind);
  end;
  writeln('Maxlength=',count);
  readln;
end.

Функции вы проходили, надеюсь..

Автор: lopata 21.03.2010 1:33

А можешь, пожалуйста, пояснить как ты это делал. Не понимаю твой код.

Автор: lopata 21.03.2010 1:54

Неправильно работает

Автор: Client 21.03.2010 1:55

пример приведи

Автор: lopata 21.03.2010 1:55

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

Добавлено через 4 мин.

ввожу строка: adeeadfcce
m = 4.
выдает 9. Хотя должно 7.
ввожу строку : accaeadad
m = 3.
выдает 9.а должно 6.

Автор: Unconnected 21.03.2010 2:03

Ну, у меня при строке abccccc и m=3 выдаёт ответ 7.

Как работает - сначала находил, сколько раз каждый символ встречается в строке, заносил эти данные в массив, потом упорядочивал его по возрастанию, а потом суммировал M элементов с конца массива, получается наибольшая длина. Могу комментарии расставить.

Ну, а чего ж ты после первого моего решения не сказала, что свой код нужен?

Автор: lopata 21.03.2010 2:05

Я же с самого начала попросила разобраться что там в моем не так)
и в самом задании конкретно указано, что должна быть функции. Комментарии расставлять не стоит, буду свой код мучать.

http://radikal.ru/F/s59.radikal.ru/i166/1003/20/c02fb0852a30.jpg.html
неверно же..

Добавлено через 5 мин.

сорри за фиговый скрин(

Добавлено через 5 мин.
Прости, пожалуйста
У тебя все верно) это у меня мозги опухли)

Автор: Unconnected 21.03.2010 2:22

Должно 9.




Неправда. Выдаёт 8, как и должно быть.

Автор: lopata 21.03.2010 2:23

Или нет...честно говоря больше ничего не понимаю

Добавлено через 4 мин.

А может сказать почему должно быть 9 и 8 ?

Автор: Unconnected 21.03.2010 2:46

'a' - 4 символа
'c' - 2 символа
'd' - 2 символа

4+2+2=8

Автор: lopata 21.03.2010 3:43

Блин.Точно.
Но:
adeeadf cce
1233124
7. должно быть



Добавлено через 2 мин.
Блин. Неважно. А что я вообще делаю не так? Чем плох мой алгоритм?

Автор: Unconnected 21.03.2010 3:54

А что будет, если видов символов в строке S будет больше M? Тебе же надо найти наибольшую возможную длину строки, значит, надо искать длиннейшие последовательности из одинаковых символов и суммировать их длины.

Автор: lopata 21.03.2010 4:01

Это понятно...А вот как найти эти длиннейшие последовательности?..

Добавлено через 2 мин.
А если это делать полным перебором?

Автор: Unconnected 21.03.2010 4:05

Бежим по строке, считаем, сколько раз каждый символ в ней встречается. Упорядочиваем эту информацию например по возрастанию, я заносил в массив. Т.е. самый последний элемент массива будет хранить длину длиннейшей последовательности, предпоследний элемент - длину второй по длине последовательности, и так далее. В итоге складываем M длин с конца.

Добавлено через 1 мин.
каким перебором, куда, зачем?..

Автор: lopata 21.03.2010 4:24

[quote name='Unconnected' date='21.03.2010 0:05' post='143223']
Бежим по строке, считаем, сколько раз каждый символ в ней встречается. Упорядочиваем эту информацию например по возрастанию, я заносил в массив. Т.е. самый последний элемент массива будет хранить длину длиннейшей последовательности, предпоследний элемент - длину второй по длине последовательности, и так далее. В итоге складываем M длин с конца.

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

Добавлено через 2 мин.
Мне кажется, должен быть какой-то другой алгоритм. Учитывая что мы сейчас на занятиях проходим алгоритмы поиска подстроки в строке..

Автор: volvo 21.03.2010 6:32

Что-то меня терзают сомнения, что это правильно, но все-таки потестируй на ВСЕХ своих тестах:

function maxChain(s: string; len: integer): integer;
var
  i: integer;
  arr: array[1 .. 255] of byte;

begin
  for i := 1 to 255 do arr[i] := 255;
  arr[1] := 1;
  for i := 2 to length(s) do
  begin
    if pos(s[i], s) < i then arr[i] := arr[i - 1]
    else arr[i] := arr[i - 1] + 1;
  end;

  i := 0;
  repeat
    inc(i)
  until arr[i + 1] > len;

  maxChain := i;
end;

var s: string;
begin
  s := 'adeeadfcce';
  writeln(maxChain(s, 4));
end.

Автор: Unconnected 21.03.2010 13:19

Проснулся сегодня и понял, что в моём коде сортировка неправильная. Так лучше:

var s:string;
    i,j,m,ind,mnind,count:byte;
    sym:array [1..255] of byte;
    mn:array[1..255] of char;

function check(c:char):boolean;
var u:byte;
begin
  check:=false;
  for u:=1 to mnind do if c=mn[u] then begin
                         check:=true;
                         break;
                       end;
end;

begin
  writeln('Vvedite Stroku');
  readln(s);
  writeln('Vvedite M');
  readln(m);
  fillchar(sym,sizeof(byte)*length(s),0);
  fillchar(mn,sizeof(char)*length(s),#0);
  ind:=0;mnind:=0;
  for i:=1 to length(s) do begin
    if not(check(s[i])) then begin
      inc(ind);inc(mnind);
      for j:=1 to length(s) do if s[j]=s[i] then inc(sym[ind]);
    end;
    mn[mnind]:=s[i];
  end;
  for i:=1 to ind-1 do begin
    for j:=i+1 to ind do begin
      if sym[i]>sym[j] then begin
        count:=sym[j];
        sym[j]:=sym[i];
        sym[i]:=count;
      end;
    end;
  end;
  count:=0;
  for i:=1 to m do begin
    inc(count,sym[ind]);
    dec(ind);
  end;
  writeln('Maxlength=',count);
  readln;
end.

Автор: lopata 21.03.2010 17:35

спасибо,volvo, но оно действительно неправильно вычисляет.
s := aaaabbccccc;
m := 1;
А значение функции 4.

Unconnected, а может все-такие проставить пожалуйста комментарии?


Добавлено через 2 мин.
Блин..
volvo, а можешь объяснить что ты делал?

Автор: Unconnected 21.03.2010 18:56

var s:string;
    i,j,m,ind,mnind,count:byte;
    sym:array [1..255] of byte; //массив, в каждой ячейке которого содержится количество вхождений в строку 
                                             //некого символа
    mn:array[1..255] of char;    //массив, в котором хранятся уже посчитанные символы. 

function check(c:char):boolean; //проверка символа на то, считали ли уже количество его вхождений в строку
var u:byte;
begin
  check:=false;
  for u:=1 to mnind do if c=mn[u] then begin
                         check:=true;
                         break;
                       end;
end;

begin
  writeln('Vvedite Stroku');
  readln(s);
  writeln('Vvedite M');
  readln(m);
  fillchar(sym,sizeof(byte)*length(s),0); //  инициализация обоих массивов
  fillchar(mn,sizeof(char)*length(s),#0);//
  ind:=0;mnind:=0; //и переменных
  for i:=1 to length(s) do begin //бежим по строке
    if not(check(s[i])) then begin //если ещё не считали количество вхождений очередного элемента, то посчитаем
      inc(ind);inc(mnind);
      for j:=1 to length(s) do if s[j]=s[i] then inc(sym[ind]); //бежим по строке и считаем вхождения
    end;
    mn[mnind]:=s[i];  //заносим в массив элемент,вхождения которого считали, чтобы не считать их снова, если 
                               //он встретится опять
  end;
  for i:=1 to ind-1 do begin  //в каждой ячейке массива sym содержится количество вхождений какого-то 
    for j:=i+1 to ind do begin //элемента. Какого, нам не важно. Сортируем этот массив, "пузырьком".
      if sym[i]>sym[j] then begin
        count:=sym[j];
        sym[j]:=sym[i];
        sym[i]:=count;
      end;
    end;
  end;
  count:=0;
  for i:=1 to m do begin //отсортировали. Длины в массиве syn хранятся по возрастанию, нам надо взять
    inc(count,sym[ind]); // M самых больших. Идём с конца (заметь, чему равно ind здесь) и суммируем эти 
    dec(ind); //элементы в count.
  end;
  writeln('Maxlength=',count);
  readln;
end.

Автор: lopata 22.03.2010 0:33

Unconnected, cпасибо большое. буду разбираться..

Автор: lopata 24.03.2010 3:42

Честно говоря, все равно что-то неверно
Потому как
s = aaaabbbccccc
m= 2
Ответ 9.
А должен быть 8
(bbbccccc)

Добавлено через 8 мин.
Или я, или ты неправильно поняли задание

Автор: Unconnected 24.03.2010 13:34

Ответ должен быть 9, aaaaccccc .

Автор: lopata 24.03.2010 16:19

я поняла почему 9. прото мне казалось, что символы должны подряд стоять...
то есть
Так aaaa bbbccccc ответ 8;
А так aaaacccccbbb 9;
А этого в самом задании не написано. Только то, что написала.

Автор: volvo 24.03.2010 16:26

Правильно казалось. Символы должны стоять именно подряд, это то, что записано в задании:
Не "состоит из символов, из которых состоит s", а "содержится в s", понимаешь? Содержится - значит целиком: bca - содержится в abcabc, а bcb - уже нет...

Update
Вот это:

function maxChain(s: string; len: integer): integer;
var
  i, offset, max: integer;
  subs: string;
begin
  max := 0;
  for i := 1 to length(s) do
  begin
    offset := 0; subs := '';
    while (i + offset <= length(s)) do
    begin
      if pos(s[i + offset], subs) > 0 then inc(offset)
      else begin
        subs := subs + s[i + offset];
        if length(subs) > len then break;
        inc(offset);
      end;
    end;

    if max < offset then max := offset;
  end;

  maxChain := max;
end;

var
  s: string;
begin
  s := 'aaaabbbccccc'; // m = 2; => 8
  // s := 'adeeadfcce';   // m = 4; => 7
  // s := 'accaeadad';    // m = 3; => 6
  // s := 'aaaabbccccc';  // m = 1; => 5
  writeln(maxChain(s, 2));
end.

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

Автор: lopata 24.03.2010 22:22

Логично...
Спасибо

Автор: lopata 24.03.2010 23:14

Тольконе совсем поняла что ты делал с Max.

Автор: volvo 24.03.2010 23:23

Искал наибольшее, что и требовалось... На каждой итерации в Offset получаем количество символов в M-буквенном слове, которое начинается с I-той позиции строки. Если среди всех Offset-ов найдем максимальный, то получим то, что требовалось в задаче: длину максимального М-буквеного слова.

Автор: lopata 24.03.2010 23:41

Всё, поняла. спасибо большое.