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

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

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

> Алгоритм поиска в множестве символов - определенной комбинации
donttouchme
сообщение 15.10.2006 8:41
Сообщение #1


Гость






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


Гость






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


Гость






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


Michael_Rybak
*****

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

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


Ищи алгоритм КПМ (Кнута-Морриса-Пратта)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Гость
сообщение 18.10.2006 13:10
Сообщение #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}


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


Michael_Rybak
*****

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

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


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

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

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

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

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

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

 



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