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

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Алгоритм поиска в множестве символов - определенной комбинации

Автор: donttouchme 15.10.2006 12:41

Помогите пожалуйста. Надо сделать вот такую вещЬ:
Разработать алгоритм поиска в некотором множестве символьных элементов определенную комбинацию символов...
Очень надеюсь на вашу помощь) wub.gif

Автор: volvo 15.10.2006 13:05

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

Автор: donttouchme 17.10.2006 0:14

ну думаю пример множества: мама мыла раму
а допустим ищем - ам
надо именно алгоритм

Автор: Michael_Rybak 17.10.2006 0:43

Ищи алгоритм КПМ (Кнута-Морриса-Пратта)

Автор: Гость 18.10.2006 17:10

Michael_Rybak - спасибо за совет! нашел!

вот:

Код

j:=0; len:=0;
{len - длина максимального качала слова X, одновременно
           являющегося концом слова y[1]..j[j]}
while (len<>n) and (j<>m) do begin
while (x[len+1]<>у[j+1]) and (len>0) do begin
{начало не подходит, применяем к нему функцию l}
len: = l[len];
end;
{нашли подходящее или убедились в отсутствии}
if x[len+1]=y[j+1] do begin
{x[1]..x[len] - самое длинное подходящее начало}
len:=len+1;
end else begin
{подходящих нет}
len:=0;
end;
j:=j+1;
end;
{если len=n, слово X встретилось; иначе мы дошли до конца
слова Y, так и не встретив X}


как теперь построить блок схему этого алгоритма?

Автор: Michael_Rybak 18.10.2006 17:47

А зачем строить блок-схему, если не секрет?

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

В твоей задаче это можно использовать так: сначала пишешь искомый фрагмент, за ним - символ-разделитель, и потом большую строку, в которой ищем. Например:

"ам#мама мыла раму"

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