VPF::KMP алгоритм - Форум программистов

box

Дата 24.4.2011, 19:08 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 506
Регистрация: 27.2.2007

Репутация: нет
Всего: 0

Взял за основу алгоритм из гугла только дописал main , при выполнении если подстрока найдена то все нормально , а если нет то прога вылетает с segmentation fault , где грабли ?

Код


#include <iostream>
#include <vector>
using namespace std;

//----------------------------
//Returns a vector containing the zero based index of
//  the start of each match of the string K in S.
//  Matches may overlap
//----------------------------
vector<int> KMP(string S, string K)
{
        vector<int> T(K.size() + 1, -1);
        for(int i = 1; i <= K.size(); i++)
        {
                int pos = T[i - 1];
                while(pos != -1 && K[pos] != K[i - 1]) pos = T[pos];
                T[i] = pos + 1;
        }

        vector<int> matches;
        int sp = 0;
        int kp = 0;
        while(sp < S.size())
        {
                while(kp != -1 && (kp == K.size() || K[kp] != S[sp])) kp = T[kp];
                kp++;
                sp++;
                if(kp == K.size()) matches.push_back(sp - K.size());
        }
        return matches;
}


int main(){
 string test="hhtetggggggtetggggjjjjjjjjjtesfffffffff";
 string test1="test";
vector<int> line( KMP( test, test1 ) );
if(line[0]>0){
 cout << "found" << endl;
 }else{
 cout << "not found" << endl;
}
}

borisbn

Дата 24.4.2011, 21:32 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 21
Всего: 135

Цитата(box @ 24.4.2011, 19:08

)

if(line[0]>0){

при пустом line и должно падать. проверять нужно так
if ( line.empty() == false ) { // не пустой. можно обращаться к line[ 0 ]
...
}
else { // пустой. к line[ 0 ] обращаться нельзя
...
}

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

box

Дата 24.4.2011, 21:43 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 506
Регистрация: 27.2.2007

Репутация: нет
Всего: 0

отлично ! спасибо !

bsa

Дата 24.4.2011, 22:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

M
bsa

box, если ответ на вопрос получен, то пометь тему решенной

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »