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

Как вивести все индексы искомых элементов (алг. Бойера-Мура)? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ как оформить в цикле додавание n слагаемых, то есть додавать цифры до тех пор пока я ненажму =. Например 1 +2 +3 +4 + . + n = и тогда выводит резуль http://www.cyberforum.ru/cpp-beginners/thread661702.html
как оформить в цикле додавание n слагаемых, то есть додавать цифры до тех пор пока я ненажму =. Например 1 +2 +3 +4 + ... + n = и тогда выводит результат?
C++ Имеется список сотрудников фирмы Имеется список сотрудников фирмы, в котором записаны: - фамилия - имя - отчество - дата рождения - телефон - адрес: - улица - номер дома - номер квартиры http://www.cyberforum.ru/cpp-beginners/thread661700.html
Стандартные способы передачи и обработки данных C++
Здравствуйте! Есть следующая задача : по СОМ порту(или другим способом LPT,RS-485…) осуществляется связь с МК , МК в реальном времени проводит вычисления и на каждом шаге может возвращать...
C++ не могу выполнить задачку для С++
Лаба по С++ как делать не могу допереть(( В некотором году, назовем его условно первым, на участке в 100 гектаров средняя урожайность ячменя составило 20 центнеров с гектара. После этого каждый...
C++ Сортировка массивов http://www.cyberforum.ru/cpp-beginners/thread661684.html
Здравствуйте, уважаемые программисты! Помогите пожалуйста разобраться с задачей. #include <iostream.h> #include <math.h> main () {
C++ Пересечение двух окружностей На плоскости даны две окружности. Требуется проверить, пересекаются ли они. Входные данные Входной файл INPUT.TXT состоит из двух строк. На каждой строке записана информация об одной окружности... подробнее

Показать сообщение отдельно
WriterMix
1 / 1 / 0
Регистрация: 06.11.2011
Сообщений: 68

Как вивести все индексы искомых элементов (алг. Бойера-Мура)? - C++

01.10.2012, 21:33. Просмотров 283. Ответов 0
Метки (Все метки)

Добрый вечер.
Задача такова: сравнить время некоторых алгоритмов поиска.
Вопрос: Дело в том, что когда алгоритм выводит все индекси искомых эелементов, время работы где-то 0,5 сек. А если без вывода - ~0,001 сек. Действительно ли время поиска должно быть таким коротким?
Проблема в том, что не могу вывести все индексы элементов, кроме первого, в алгоритме Бойера-Мура. Помогите, пожалуйста, мне это реализовать.
Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int BMsearch(char* str, char* word, int lenWord) 
{
    char* inits = str;
    char* initp = word;
 
    while(*word != '\0') word++;
    int* jump_table=(int*) calloc(128, sizeof(int));
    int count=0;
 
    while(word != initp) {
        word--;
        jump_table[*word]=count;
        count++;
    }
 
    char* stmp=0;
    char* iter=0;
    int shift=0;
    int bad_count=0;
    int bcount=0;
    while(*str != '\0')
    {
        bcount=0;
        bad_count=lenWord;
        stmp = str+ (lenWord-1);
        iter = word + (lenWord-1);
        while(*stmp == *iter) {
            bad_count--;
            bcount++;
            stmp--;
            iter--; 
            if(bcount==lenWord)
                cout<<str-inits<<" "; 
                return str-inits;
        }
 
        //jump table
        if(jump_table[*stmp] == 0) {
            // the character not found in pattern
            shift=bad_count;
        } else {
            shift=jump_table[*stmp];
            (shift - bcount < 1)?shift = 1: shift = shift-bcount;
        }
        str += shift;
    }
    //not found
    return -1;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru