Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Алгоритм прямого поиска. Реализация на С++ - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ windows forms http://www.cyberforum.ru/cpp-beginners/thread861571.html
Можно ли писать приложения на C++ c использованием .Net windows forms или только на c#?
C++ Класс как стандартный контейнер Здорова господа! Опять есть условие задачи: Напишите такие классы, чтобы Vector из 16.2.1 и Vector из 16.2.2 могли использоваться как стандартные контейнеры. От Vector из 16.2.1:... http://www.cyberforum.ru/cpp-beginners/thread861569.html
C++ Решение нелинейного уравнения методом итераций в с++
Помогите пожалуйста решить нелинейное уравнение x^2-2x-1 = 0 промежуток от 0 до 3. Находил несколько кусков кода но так и не понял как туда вставить уравнение.
C++ Определить принадлежность точки с координатами (x, y) закрашенной области
помогите разобраться как правильно записать условия попадания точки в заданную область(правильно описать A и B, я разделил фигуру на 2 части) в геометрии у меня не особо получается разбираться) ...
C++ Пересечение двух окружностей http://www.cyberforum.ru/cpp-beginners/thread861522.html
Есть такая задачка. Вам даны две окружности в плоскости. Найдите все их различные точки пересечения. В силу большой требуемой точности рекомендуется использовать более чем 8-байтные...
C++ Манипуляторы Ребята, проблема с манипуляторами.. Вместо того чтобы были пустые места, программа выдает нули(( void view(HANDLE hrFile) { Miami_Heat Club; int num = 0; DWORD dwCount; ... подробнее

Показать сообщение отдельно
trunks1994
0 / 0 / 0
Регистрация: 11.01.2013
Сообщений: 12

Алгоритм прямого поиска. Реализация на С++ - C++

11.05.2013, 16:13. Просмотров 2040. Ответов 1
Метки (Все метки)

может кто-то написать алгоритм прямого поиска на С++?
очень надо...
суть поиска такова:

Алгоритм прямого поиска


Идея алгоритма:
1. I=1,
2. сравнить I-й символ массива T с первым символом массива W,
3. совпадение → сравнить вторые символы и так далее,
4. несовпадение → I:=I+1 и переход на пункт 2,

Условие окончания алгоритма:
1. подряд М сравнений удачны,
2. I+M>N, то есть слово не найдено.

Сложность алгоритма:
Худший случай. Пусть массив T→{AAA….AAAB}, длина │T│=N, образец W→{A….AB}, длина │W│=M. Очевидно, что для обнаружения совпадения в конце строки потребуется произвести порядка N*M сравнений, то есть O(N*M).

Недостатки алгоритма:
1. высокая сложность — O(N*M), в худшем случае – Θ((N-M+1)*M);
2. после несовпадения просмотр всегда начинается с первого символа образца и поэтому может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени);
3. информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru