VPF::Алгоритм Бойлера-Мура - Форум программистов

KatyaKatch

Дата 3.11.2014, 12:57 (ссылка)

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

Загрузка ...

Новичок

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

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

Мой алгоритм выводит позицию первого вхождения подстроки в строке, а мне нужно, чтобы выводил позиции всех вхождений. Помогите пожалуйста!

Код


#include <cstdlib>
#include <iostream>
#include <string>

#define ALPHABET_LEN 255 
#define NOT_FOUND patlen 
#define max(a, b) ((a < b) ? b : a)

using namespace std;

void make_delta1 (int *delta1, char *pat, long int patlen)
{
    int i;
    for (i=0; i < ALPHABET_LEN; i++) delta1[i] = NOT_FOUND;
    for (i=0; i < patlen-1; i++) delta1[pat[i]] = patlen-1-i;
}

int is_prefix (char *word, int wordlen, int pos) 
{
    int suffixlen = wordlen - pos;
    for (int i = 0; i<suffixlen; i++) 
    {
        if (word[i] != word[pos+i]) return 0;
    }
    return 1;
}
int suffix_length (char *word, int wordlen, int pos)
{
    int i;
    for (i = 0; (word[pos-i] == word[wordlen-1-i]) && (i < pos); i++);
    return i;
}

void make_delta2(int *delta2, char *pat, long int patlen)
{
    int last_prefix_index = patlen-1;
    int p;
    for (p=patlen-1; p>=0; p--) 
    {
        if (is_prefix(pat, patlen, p+1)) last_prefix_index = p+1;
        delta2[p] = last_prefix_index + (patlen-1 - p);
    }
    for (p=0; p < patlen-1; p++)
    {
        int slen = suffix_length(pat, patlen, p);
        if (pat[p-slen]!=pat[patlen-1-slen]) delta2[patlen-1-slen]=patlen-1-p+slen;
    }
}

int boyer_moore (char *string, char *pat) 
{
    long int stringlen = strlen(string);
    long int patlen =strlen(pat);
    int delta1[ALPHABET_LEN];
    make_delta1(delta1, pat, patlen);
    int *delta2 = new int [patlen * sizeof(int)];
    make_delta2(delta2, pat, patlen);
    int i = patlen-1;
    while (i < stringlen)
    {
        int j = patlen-1;
        while (j >= 0 && (string[i] == pat[j])) 
        {
            --i; --j;
        }
        if (j < 0) 
        {
            delete delta2;
            return i+2;
            int k=i+2;
            for (int f=0;f<=k+1;f++)
            string[f]=0;
            
        }
        i += max(delta1[string[i]], delta2[j]);
        
    }

    delete delta2;
    return NULL;
}

int main()
{
    char *string="ceea babc";
    char *pattern="a";
    long int stringlen = strlen(string);
    for (int l=0;l<stringlen;l++)
    {
        cout << boyer_moore(string,pattern)<<" "<<endl;  
    }
    return EXIT_SUCCESS;
}

Romikgy

Дата 3.11.2014, 13:27 (ссылка)

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

Загрузка ...

Любитель-программер

Профиль
Группа: Участник Клуба
Сообщений: 7326
Регистрация: 11.5.2005
Где: Porto Franco Odes sa

Репутация: 8
Всего: 146

Код


int i;
while ((i= boyer_moore(string+i,pattern))>0)
{
cout << i<<" "<<endl;  
i++;
}

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

Владение русской орфографией это как владение кунг-фу — истинные мастера не применяют его без надобности.

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