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

Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула. - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Указатели и ссылки [С++] http://www.cyberforum.ru/cpp-beginners/thread423728.html
Всем привет. я тут программу делаю. Цель: определить,принадлежит ли точка заданному промежутку(а точнее лежит внутри или снаружи фигуры). Координаты храню в массивах(по 2 значения: x и y.). Вопрос такой: можно ли создать указатель(или ссылку),который бы хранил область памяти на массив,чтобы потом им можно было манипулировать,как и массивом? к примеру: int a; int &y= a; &y = 2; &y = 5; //...
C++ сумма элементов матрицы Здравствуйте. Такая задача: В массиве А (m = n) сумму элементов над главной диагональю поделить на сумму элементов под главной диагональю. Элементы под глав-ной диагональю рассортировать по убыванию. Помогите найти суммы элементов. #include <iostream> #include <iomanip> using namespace std; int main() { setlocale(LC_ALL, "Russian"); http://www.cyberforum.ru/cpp-beginners/thread423726.html
C++ Функции (Даны три вещественные квадратные матрицы 4-го порядка)
Даны три вещественные квадратные матрицы 4-го порядка. Напечатать ту из них,норма которой наименьшая (считать, что такая матрица одна). В качестве нормы матрицы взять максимум абсолютных величин ее элементов Заранее спасибо)) пож...мне очень срочно у меня через 3 дня экзамен!
Рекурсия(вычислить 1*2*3*...n+2*3*4*...(n-1)+3*4*5*(n-2)+...) C++
дано натуральное число n. вычислить 1*2*3*...n+2*3*4*...(n-1)+3*4*5*(n-2)+... Очень срочно!! Заранее спасибо!!
C++ Оформить в циклке http://www.cyberforum.ru/cpp-beginners/thread423639.html
temp = a; temp = a; temp = a; temp = a; temp = a; temp = a; a = a; a = a; a = a;
C++ Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. Добрый вечер всем! Возник вопрос - прошу помощи. Речь об STL... В чем проблема собственно: почему для использования у множества с пользовательскими объектами метода find() не нужен перегруженный оператор== ??? Для тех же списков или векторов, да и для двухсторонних очередей тоже, наличие == обязательно (для все того же find(), только тут это алгоритм). Тоже самое с count(). Заранее благодарен.... подробнее

Показать сообщение отдельно
asm
 Аватар для asm
62 / 35 / 1
Регистрация: 05.10.2011
Сообщений: 137
07.01.2012, 15:32     Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула.
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include "stdafx.h"
#include <stdlib.h>
 
 
int BoyerMooreHorspool(char *haystack, char *needle)
{
        int i,j,k, needle_len = 0,haystack_len = 0;
        int needle_table[256]; // таблица символов
 
        char *p; // указатель на символ
        for ( p = needle; *p; *p++) // подсчет кол-ва символов в needle
                ++needle_len;
        for ( p = haystack; *p; *p++) // подсчет кол-ва символов в haystack
                ++haystack_len;
 
        if (needle_len < haystack_len) // 
        {
                for (i = 0; i < 256; i++) // в таблицу заносится для каждого символа длина needle
                        needle_table[i] = needle_len; 
 
                for (i = 1; i < needle_len; i++) // каждому символу из таблицы ставиться в соответствие его порядковый номер из needle
                        needle_table[needle[i-1]] = needle_len-i;
 
                i = needle_len; // i - счетчик текущего последнего символа в haystack 
                j = i; // j - счетчик в needle кол-ва одинаковых символов (совпадающих с таблицей) с конца 
 
                while (j > 0 && i <= haystack_len) // если j==0 то совпадение найдено
                {
                        j = needle_len; // заново выполняем присваивание, чтобы сравнивать строки с конца
                        k = i; // k - счетчик текущего символа в haystack
                               // j - счетчик текущего символа в needle
                        while (j > 0 && haystack[k-1] == needle[j-1]) // сравнение последних симолов
                        { // если раны, то сравниваем предыдущие
                                --k;
                                --j;
                        }
                        i+=needle_table[haystack[i-1]]; // сдвигаем шаблон на следующий совпадающий символ из таблицы и haystack
                        // т.е. в needle ищется (т.е. уже дан в таблице) последний сравниваемый символ из haystack
                }
 
                if (k > haystack_len - needle_len) // если k выходит за пределы сравнения, то ...
                        return 0;
                else return k+1; // иначе k== текущая позиция подстроки needle в строке haystack 
                // ВНИМАНИЕ! k показывает смещение в haystack, предполагая, что строка начинается с 1 (единицы)
        }
        else return 0; // if (needle_len >= haystack_len)
}
 
//-------------------------------------------------------------------
 
int main(int argc, char* argv[])
{
    char s1[] = "abDcDABcd";
    char s2[] = "cDA";
 
    printf("haystack: %s\n", s1);
    printf("needle: %s\n", s2); 
    
    printf("result: %i\n", BoyerMooreHorspool(s1,s2));
 
    system("pause");
    return 0;
}
Добавлено через 1 минуту
Цитата Сообщение от InfernalA1D Посмотреть сообщение
Где ошибка?!
видимо в строке 32

Добавлено через 4 минуты
Код отсюда: http://ru.wikipedia.org/wiki/%D0%90%...83%D0%BB%D0%B0
Сам почитал, разобрался, добавил комментарии.
 
Текущее время: 05:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru