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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
sylar156
Сообщений: n/a
#1

алгоритм быстрый поиск - C++

14.12.2010, 23:01. Просмотров 1490. Ответов 0
Метки нет (Все метки)

нашел в интернете описание алгоритма быстого поиска

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

После попытки совмещения x и y [ i , i + m - 1 ], длина сдвига - не менее 1. Таким образом, символ y [ i + m ] обязательно будет вовлечен в следующую попытку, а значит, может быть использован в текущей попытке для сдвига плохого символа. Модифицируем функцию плохого символа, чтобы принять в расчет последний символ х:

bc[ a ] = min { j | 0 <= j <= m и x[ m - 1 - j ] = a }, если a встречается в x,

bc[ a ] = m в противоположном случае.

Сравнения текста и образца могут производиться в любом порядке. Несмотря на маловероятный худший случай, алгоритм демонстрирует прекрасное поведение на практике.


функция OUTPUT возвращает позицию начала совпадения относительно начала текста.

константа ASIZE - размер алфавита
реализация на C

Код
void QS( char *y, char *x, int n, int m)
{
 int i, qs_bc[ ASIZE ];
 
 /* Preprocessing */
 for ( i = 0; i < ASIZE; i++ ) qs_bc[ i ] = m + 1;
 for ( i = 0; i < m; i ++ ) qs_bc[ x[i] ] = m - i;
 
 /* Searching */
 i = 0; 
 while ( i <= n - m ) {
    if ( memcmp( &y[ i ], x, m ) == 0 ) OUTPUT( i );
   i += qs_bc[ y[ i + m ] ];             /* shift */
 }
}


возник вопрос
как реализовать функцию output ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.12.2010, 23:01
Здравствуйте! Я подобрал для вас темы с ответами на вопрос алгоритм быстрый поиск (C++):

Самый быстрый алгоритм Факториала - C++
Всем привет ! Как можно реализовать факториал за log(n) . Помогите плиз ! Знаю ,что можно рекурсией . Но этот алгоритм не быстрый. Помогите...

Быстрый поиск - C++
Здравствуйте. Нужно выполнить поиск i-го вхождения заданного элемента в исходном наборе чисел. Написал такой поиск, но работает...

Быстрый алгоритм для подсчета количества делителей числа - C++
Быстрый алгоритм для подсчета количества делителей натурального числа 1 &lt;= x &lt;= 1018. Помогите реализовать такой. Дело в том, что должно...

Самый быстрый алгоритм на с++ для поиска изображений с погрешностью - C++
Подскажите самый быстрый алгоритм для поиска одного изображения на другом с погрешностью. То есть загружается два изображения и происходит...

Быстрый поиск элемента - C++
Добрый день всем! Такой вопрос - есть у меня строка из 64-х чаров. Мне приходит новый чар и нужно найти какой индекс у такого же чара в...

Быстрый поиск в мапе - C++
Есть мапа вида : std::map&lt;size_t, std::string&gt; Нужно найти элемент меньший или равный элементу из rbf с конца мапы. Есть ли быстрый...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2010, 23:01
Привет! Вот еще темы с ответами:

Быстрый поиск по полям в коллекции - C++
Есть коллекция объектов класса с разными полями. Нужно организовать быстрый поиск первого элемента (может потом множества элементов) по...

Быстрый поиск минимального числа - C++
подскажите быстрый алгоритм поиска второго минимального числа в массиве?

Быстрый поиск супернатуральных чисел - C++
Натуральное число будем называть супернатуральным, если в своем десятичном виде оно не содержит единиц, а произведение всех его цифр равно...

Быстрый поиск в векторе из pair - C++
Пытаюсь сделать вектор: vector&lt; pair&lt;string, string&gt; &gt; myVect; По идее, проще воспользоваться чем-то вроде map или unordered_map,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru