InfernalA1D
1

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

06.01.2012, 23:48. Показов 5945. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Функция получает ссылки на две переменные: 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;
}
Где ошибка?!
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.01.2012, 23:48
Ответы с готовыми решениями:

Алгоритм Бойера-Мура поиска подстроки в строке (Js -> C++)
Помогите реализовать алгоритм для с ++ &lt;html&gt; &lt;head&gt; &lt;meta charset=&quot;utf-8&quot; /&gt;...

Поиск подстроки в строке(алгоритм Бойера-Мура)
Программа находит шаблоны в строке алгоритмом Бойера-Мура и находить должна в строке которая...

Поиск подстроки в строке: алгоритм Рабина-Карпа или Бойера-Мура(-Хорспула)
Необходимо реализовать алгоритм Рабина-Карпа или Бойера-Мура(-Хорспула), если нам дана подстрока,...

Алгоритм поиска образа в строке. Алгоритм Бойера-Мура
# Лабораторная работа № 1 # Поиск образа в строке def forming_d(pattern): &quot;&quot;&quot; Формируем...

3
62 / 35 / 3
Регистрация: 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 раз
вообще код надо бы комментировать, а то сложно читать вот так...

Не по теме:

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

0
InfernalA1D
07.01.2012, 07:10 3
Цитата Сообщение от asm Посмотреть сообщение
for (i = 1; i < needle_len; i++) needle_table[needle[i-1]] = needle_len-i;
это таблица смещений.
j не всегда больше нуля т.к. там есть декремент во вложенном цикле. Да и цикл то с предусловием.
62 / 35 / 3
Регистрация: 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/%... 0%BB%D0%B0
Сам почитал, разобрался, добавил комментарии.
1
07.01.2012, 15:32
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.01.2012, 15:32
Помогаю со студенческими работами здесь

Поиск методом Бойера-Мура(подстроки в строке)
Сколько ищу в инете и в куче книг по си шарпу -- нету материала как этот метод поиска ...

Алгоритм Бойера и Мура
Добрый день! Помогите пожалуйста написать на С++ алгоритм Бойера и Мура Добавлено через 7...

алгоритм Бойера-Мура
Всем привет! Помогите исправить ошибку пожалуйста! unit Unit1; interface uses ...

Алгоритм Бойера — Мура
Люди добрые помогите с задачей! Необходимо Алгоритмом Бойера — Мура найди вхождения строки в...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru