Форум программистов, компьютерный форум, киберфорум
C++ Builder
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.94/34: Рейтинг темы: голосов - 34, средняя оценка - 4.94
2 / 2 / 1
Регистрация: 12.02.2011
Сообщений: 49

Алгоритм Хорспула (поиск подстроки)

22.11.2011, 20:34. Показов 6597. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Задали курсовую по алгоритму Хорспула (поиска подстроки), на консоли (VS c++ 2010) сделал, всё работает ( по крайней мере на англицком алфавите) начал перекладывать на C++ Builder6 ( примитивно пока) не хочет работать , чую проблема в моем не понимании типа AnsiString. Может кто подскажет куда рыть то.
код для консоли
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
int HorspoolMatch(string T,string P)
{       
        int n=T.length();// длина строки
        
        int m=P.length();// длина шаблона 
    
        int Slide[255];// талица сдвигов на 256 символов
        for(int i=0; i<255; i++)
                Slide[i]=m;// таблица сдвигов заполняется длинной образца
        for(int l=0; l<m-1; l++)         // в ТС 
        { Slide[P[l]] = m -1- l;}
        int i=m-1;//позиция правого конца образца
 
        while(i <= (n - 1))// пока првый конец не достигнет правого конца строки
        {
            int k=0;// количество совпавших символов
                while(k<= m-1&& P[m-1-k]==T[i-k])// пока количество совпадений меньше образца и           
                {
                                              // если  текущий символ совпадает с символом в строке
                           k=k+1;             // увеличиваем к  на 1
                }
            
          if (k==m)                  // проверяем чего это из предыдущего цикла вывалилась программа- на совпадение 
            return i-m+1;          // если совпадение полное то  возвращаем  позицию первого совпавшего симовола в строке 
         
          else                       // если не все совпали 
                {   cout<<"Смещение "<<Slide[T[i]]<<endl ;
                    i= i+ Slide[T[i]];    //  сдвигаем i(позиция правого конца шаблона) по таблице сдвигов
                    
                  }
 
 
            
 
        }// если программа вывалилась из внешнего цикла то усё - 
          //ничего она не нашла и дошла до конца текста
        
        
            return -1;// пуляем сообщение о неудаче
}
 
//void main()
int main()
{
        setlocale (LC_ALL, "Russian");
         string T;
       
        string P;//строка, которую ищем
        int pos;
        cin>>T;// 
        cout<< endl;
        cin >>P;//
        cout<< endl;
        cout<<endl;
        pos=HorspoolMatch(T,P);
     if( pos==-1)
         cout << "Поиск не дал результатов :-(((    "<< endl;
     else 
         cout<<" Искомое сочетание найдено !!!  С позиции   "<< pos<<endl;
     system("PAUSE");
     return EXIT_SUCCESS;    
}
А вот код для Билдера
содежимое заголовочного файла для фукции поиска изменено с учетом того , что индекс первого символа не 0 а 1

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
#include <cstdlib>
#include <iostream>
#include <dstring.h>
#include <sysutils.hpp>
 using namespace std;
             int HorspoolMatch(AnsiString T,AnsiString P)
{
        int n=T.Length();// длина строки
 
        int m=P.Length();// длина шаблона
 
        int Slide[255];// талица сдвигов на 256 символов
        for(int i=1; i<255; i++)
                Slide[i]=m;// таблица сдвигов заполняется длинной образца
        for(int l=1; l<m; l++)         // в ТС
        { Slide[P[l]] = m -l;}
        int i=m;//позиция правого конца образца
 
        while(i <= (n-1) )// пока првый конец не достигнет правого конца строки
        {
            int k=0;// количество совпавших символов
                while(k<= m && P[m-1-k]==T[i-k])// пока количество совпадений меньше образца и
                {
                                              // если  текущий символ совпадает с символом в строке
                           k=k+1;             // увеличиваем к  на 1
                }
 
          if (k==m)                  // проверяем чего это из предыдущего цикла вывалилась программа- на совпадение
            return i-m+1;          // если совпадение полное то  возвращаем  позицию первого совпавшего симовола в строке
 
          else                       // если не все совпали
                {   //cout<<"Смещение "<<Slide[T[i]]<<endl ;
                    i= i+ Slide[T[i]];    //  сдвигаем i(позиция правого конца шаблона) по таблице сдвигов
 
                  }
 
 
            
 
        }// если программа вывалилась из внешнего цикла то усё -
          //ничего она не нашла и дошла до конца текста
        
 
            return -1;// пуляем сообщение о неудаче
}
далее код для обработчика событий
C++
1
2
3
4
5
6
7
8
9
10
11
12
void __fastcall TForm1::Button1Click(TObject *Sender)
{
 
 T= Edit1->Text;
 P= Edit2->Text;
 pos=HorspoolMatch(T,P);
     if( pos==-1)
           Label3->Caption="Поиск не дал результатов :-(((    ";
     else
         Label3->Caption=" Искомое сочетание найдено !!! УРАААА :-))) !!!!  С позиции   ";
 
}
компилируется, идет на выполнение, ввожу строку и подстроку на английском нажимаю "искать" и выкидывает сообщение :
Project kurcovai.exe raised exception class ERangeError with message" . Process stopped. Use Step or Run to continue.
отключаю вызов фукции всё окей, значит вся проблема в функции а точнее в типе AnsiString и размере таблицы. Может коды символов в AnsiString не с 0 по 255, и поетому и обращение к строке идет не по тем индексам?
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
22.11.2011, 20:34
Ответы с готовыми решениями:

Подскажите: Поиск подстроки в AnsiString
Доброе время суток. Пишу на Borland C++ в Билдере и возникает проблема.. Мне надо сравнить две строки, допустим: AnsiString...

Поиск подстроки на странице в CppWebBrowser
Доброе время суток. Подскажите пожалуйста как можно реализовать поиск подстроки в тексте страницы, загруженной в CppWebBrowser, и если...

Поиск подстроки, нечувствительный к регистру
Есть ли встроенные функции для поиска подстроки в AnsiString, нечувствительный к регистру (т.е. строчные и прописные буквы считаются...

2
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
 Аватар для volvo
33399 / 21509 / 8236
Регистрация: 22.10.2011
Сообщений: 36,907
Записей в блоге: 12
22.11.2011, 23:20
Цитата Сообщение от Нач_физик Посмотреть сообщение
содежимое заголовочного файла для фукции поиска изменено с учетом того , что индекс первого символа не 0 а 1
Зачем? Проще будет все оставить как есть, но при обращении к P[] и T[] добавлять к индексу 1. Вот так:

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
int HorspoolMatch(AnsiString T, AnsiString P)
{
    int n = T.Length();
    int m = P.Length();
 
    int Slide[255];
    for(int i=0; i<255; i++)
        Slide[i]=m;
 
    for(int l=0; l<m-1; l++)
    {
        Slide[P[l+1]] = m -1- l; // <--- *** Раз ***
    }
 
    int i=m-1;
    while(i <= (n - 1))
    {
        int k=0;
        while(k<= m-1&& P[m-1-k+1]==T[i-k+1]) // <--- *** Два, три (можешь "+1-1" убрать) ***
        {
            k=k+1;
        }
 
        if (k==m)
            return i-m+1;
        else
        {
            i= i+ Slide[T[i+1]]; // <--- *** Четыре ***
        }
    }
    return -1;
}
Добавлено всего 8 символов, а какой эффект, программа заработала и не выбрасывает исключения
1
2 / 2 / 1
Регистрация: 12.02.2011
Сообщений: 49
23.11.2011, 19:21  [ТС]
Удивительно, но правда заработала. Спасибо.
А на русском вводе не хочет работать( не находит подстроку) почему?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
23.11.2011, 19:21
Помогаю со студенческими работами здесь

Поиск подстроки между определенными символами
Здравствуйте! Помогите плиз,как это можно реализовать. Допустим у нас есть строка: Мы с мамой пошли в парк им. Горького, а потом...

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

Ошибка в функции поиска подстроки в строке. Алгоритм Бойера-Мура-Хорспула.
Функция получает ссылки на две переменные: haystack и needle строкового типа. В haystack должна содержаться строка, в которой будет...

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

Поиск подстроки в строке (алгоритм Кнута-Морриса-Пратта)
Требуется написать программу которая ищет количество вхождений подстроки в строке, используя алгоритм кнута-морриса-пратта


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
Символические и жёсткие ссылки в Linux.
algri14 15.03.2026
Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это дополнительная запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru