поиск в строке, помигите найти ошибку Опции

[lopata]

Строка называется 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 *)

Сообщение отредактировано: lopata - 20.03.2010 16:00

[Unconnected]

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

[lopata]

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

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

[Unconnected]

Можно так:

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]

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

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

[Unconnected]

Тогда так:

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]

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

[lopata]

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

[Client]

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

[lopata]

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

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

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

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

[Unconnected]

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

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

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

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

[lopata]

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

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

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

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


неверно же..

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

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


неверно же..

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

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

Сообщение отредактировано: lopata - 20.03.2010 22:15

[Unconnected]

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

Должно 9.

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

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

Сообщение отредактировано: Unconnected - 20.03.2010 22:22

[lopata]

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

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

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

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

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

[Unconnected]

ввожу строку : accaeadad
m = 3.

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

4+2+2=8

[lopata]

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

4+2+2=8

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



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

[Unconnected]

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

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

[lopata]

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

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

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

[Unconnected]

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

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

[lopata]

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

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

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