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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.79
InfernalA1D
Сообщений: n/a
06.01.2012, 23:48     Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула. #1
Функция получает ссылки на две переменные: haystack и needle строкового типа. В haystack должна содержаться строка, в которой будет осуществлён поиск, а needle должна содержать подстроку, которую надо найти. В результате выполнения процедуры переменная функция вернёт номер позиции (при нумерации с единицы), начиная с которого подстрока needle входит в строку haystack, или 0, если вхождения нет.


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
int CP7Dlg::BM(char *haystack, char *needle)
{   UpdateData(1);
        int i=0,j=0,k=0, needle_len=0, haystack_len=0;
        char needle_table[256];
        
        needle_len=edit2.GetLength();
        haystack_len=edit1.GetLength();
                        
    if (needle_len <= haystack_len)
        {
                for (i = 0; i < 256; i++)
                        needle_table[i] = needle_len;
 
                for (i = 1; i < needle_len; i++)
                        needle_table[needle[i-1]] = needle_len-i;
 
                i = needle_len;
                j = i;
 
                while ( j > 0 && i <= haystack_len)
                {
                        j = needle_len;
                        k = i;
                        while ( j > 0 && haystack[k-1] == needle[j-1])
                        {
                                --k;
                                --j;
                        }
                        i+=needle_table[haystack[k-1]];
                
                }
                if (i > haystack_len)
                        return 0;
                else return k+1;
        }
        else return 0;
}
Где ошибка?!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.01.2012, 23:48     Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула.
Посмотрите здесь:

C++ Алгоритм Бойера-Мура
C++ Алгоритмы поиска подстроки в строке
C++ Очень прошу разъяснить код алгоритма Бойера-Мура
C++ Функция поиска подстроки в строке
C++ Поиск подстроки в строке(алгоритм Бойера-Мура)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
asm
 Аватар для asm
62 / 35 / 1
Регистрация: 05.10.2011
Сообщений: 137
07.01.2012, 02:19     Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула. #2
вопрос, что делает эта строчка?
Цитата Сообщение от InfernalA1D Посмотреть сообщение
for (i = 1; i < needle_len; i++) needle_table[needle[i-1]] = needle_len-i;
и еще:
C++
1
2
3
while ( j > 0 && i <= haystack_len) 
{ 
j = needle_len; // j всегда > 0 (бесконечный цикл) или цикл выполняется 1 раз
вообще код надо бы комментировать, а то сложно читать вот так...

Не по теме:

куда деваются мои комментарии? мистика, мистика...

InfernalA1D
Сообщений: n/a
07.01.2012, 07:10     Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула. #3
Цитата Сообщение от asm Посмотреть сообщение
for (i = 1; i < needle_len; i++) needle_table[needle[i-1]] = needle_len-i;
это таблица смещений.
j не всегда больше нуля т.к. там есть декремент во вложенном цикле. Да и цикл то с предусловием.
asm
 Аватар для asm
62 / 35 / 1
Регистрация: 05.10.2011
Сообщений: 137
07.01.2012, 15:32     Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула. #4
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
Сам почитал, разобрался, добавил комментарии.
Yandex
Объявления
07.01.2012, 15:32     Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула.
Ответ Создать тему
Опции темы

Текущее время: 23:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru