IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Алгоритм поиска в множестве символов - определенной комбинации
сообщение
Сообщение #1


Гость






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


Гость






Пример исходных данных и результата поиска приведи...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






ну думаю пример множества: мама мыла раму
а допустим ищем - ам
надо именно алгоритм
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ищи алгоритм КПМ (Кнута-Морриса-Пратта)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






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}


как теперь построить блок схему этого алгоритма?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

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

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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 26.09.2017 9:05
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"