2

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

Принцип алгоритма можно посмотреть здесь.

Пример:

подстрока:        ДАННЫЕ
строка:           ДАН ТЕКСТ В НЁМ ДАНЫ ДАННЫЕ
вывод программы:  6 5 12 18 22 27 26 25 24 23 22

Посинение к примеру:

ДАННЫЕ*
5422166
 

ДАН ТЕКСТ В НЁМ ДАНЫ ДАННЫЕ
ДАННЫЕ
------ДАННЫЕ
      ------ДАННЫЕ
            ----ДАННЫЕ
                -----ДАННЫЕ
         1         2   позиция в тексте (десятки)
1234567890123456789012 позиция в тексте (единицы)


все проверенные индексы: 6 5 12 18 22 27 26 25 24 23 22

Входные данные:

В первой строке файла in.txt содержится подстрока для поиска (подстрока не содержит символа '\n'). Длина строки всегда не больше 17-и символов.

Всё остальное в файле in.txt является строкой, в которой нужно искать подстроку (т.е. строка может содержать символ '\n'). Также, важно отметить, что строка, в которой надо искать, не ограниченна по длине.

Мой код:

#include <string.h> 
#include <stdlib.h>
#include <stdio.h>   

typedef int bool;
enum { false, true }; 

int main(void) {   
    FILE *file = fopen("in.txt", "r");
    unsigned char template[20] = {'\0'}, text[256] = {'\0'};  //template - то что ищем, text - где ищем
    
    /*
    Не самая изящная реализация ввода данных 
    Рассчитана на то, что по условию template - НЕ содержит символов '\n', а text МОЖЕТ содержать символы '\n' )
    */
    bool wasNewLine = false; 
    int k = 0;
    unsigned char c = '\0';
    while (fscanf(file, "%c", &c) != EOF)
    { 
        if (c == '\n' && !wasNewLine)
        {
            k = 0;
            wasNewLine = true;
            continue;
        } 
        if (wasNewLine)
        {
            text[k] = c;
        }
        else
        {
            template[k] = c; 
        }
        k++;
    } 
    fclose(file); 

    /*
    Построение таблицы - sample на основе строки template.
    Пример:
    template: ДАННЫЕ
    sample:   542216  
    */
    int N = strlen(template), sample[16] = {0}, i, j, lastChar, shiftIndex, textLen = strlen(text);    
    for (i = N-2; i > -1; i--) {
        sample[i] = N-i-1;
        for (j = N-2; j > i; j--) {
            if (template[i] == template[j]) {
                sample[i] = sample[j];
                break;
            }
        }
    } 
    sample[N-1] = N; 
    for (i = N-1; i > -1; i--) {
        if (template[N-1] == template[i]) { 
            sample[N-1] = sample[i];
            break;
        }
    }   


    /*
    Сам алгоритм Бойера-Мура 
    */
    i = 0, j = N-1, lastChar = text[N-1];  
    while (j+i < textLen) {
        printf("%d ",j+i+1);
        if (text[j+i] != template[j] || j == 0) { 
            shiftIndex = -1; 
            for (int k = 0; k < N; k++) {
                if (lastChar == template[k]) {
                    shiftIndex = k;
                    break;
                } 
            }  
            if (shiftIndex == -1) {
                i += N;
            }
            else {
                i += sample[shiftIndex] ;
            }
            j = N-1;
            lastChar = text[j+i]; 
        }
        else {
            j--;
        }
    } 
   
    return 0;
}

Мой код работает идеально, за одним исключением - когда размер текста, в котором надо искать, становится слишком большим и я уже не могу уместить его в один массив text.

Я пробовал считывать text по кускам размером равным длине подстроки. Но такой подход не сработал (либо я где-то ошибся).

Код со считыванием text'a по кускам. (также вынес некоторые части предыдущего кода в отдельные функции)

#include <string.h> 
#include <stdlib.h>
#include <stdio.h>    

void fillSample(int *sample, char *template, int N)
{
    for (int i = N-2; i > -1; i--) {
        sample[i] = N-i-1;
        for (int j = N-2; j > i; j--) {
            if (template[i] == template[j]) {
                sample[i] = sample[j];
                break;
            }
        }
    }
    sample[N-1] = N;
    for (int i = N-1; i > -1; i--) {
        if (template[N-1] == template[i]) { 
            sample[N-1] = sample[i];
            break;
        }
    }   
}

int BoyerMoor(char* text, int* sample, char* template, int N, int shift){ 
    int i = 0, j = N-1, textLen = strlen(text), shiftIndex;
    char lastChar = text[N-1];   
    i = 0;
    while (j+i < textLen) {
        printf("%d ",j+i+1+shift );
        if (text[j+i] != template[j] || j == 0) { 
            shiftIndex = -1;

            for (int k = 0; k < N; k++) {
                if (lastChar == template[k]) {
                    shiftIndex = k;
                    break;
                } 
            } 

            if (shiftIndex == -1) {
                i += N;
            }
            else {
                i += sample[shiftIndex] ;
            }
            j = N-1;
            lastChar = text[j+i]; 
        }
        else {
            j--;
        }
    }
    return i; //return next shift
}

int main(void) {     
    FILE *file = fopen("in.txt", "r");

    char template[17] = {'\0'}, text[256] = {'\0'}; 
    int N = 0, shift = 0; 
    char c = '\0';
    while (fscanf(file, "%c", &c) != EOF)
    { 
        if (c == '\n') 
            break; 
        template[N] = c;  
        N++;
    }

    int sample[17] = {0};    
    fillSample(sample, template, N); 
 
    //Обрабатываю текст по кускам длиной N, 
    int fs = fscanf(file, "%c", &c);
    while (fs != EOF)
    { 
        for(int i = 0; i < N; i++)
        { 
            if (fs == EOF)
                break;
            text[i] = c; 
            fs = fscanf(file, "%c", &c);   
        }
         
        
        shift += BoyerMoor(text, sample, template, N, shift);  
        memset(text, '\0', sizeof text); 
    } 

    fclose(file);  
 
    return 0;
}

Подскажите как можно видоизменить мой код или просто подскажите подход который бы смог работать на больших данных.

1
  • 1
    Эээ.. Текст нужно считывать по кускам, перекрытие которых между собой равно длине искомой строки.
    – MBo
    31 окт 2020 в 8:05

1 ответ 1

4

Если текст читать кусками размером со строку поиска, то почти наверняка её пропустишь:
Ищем "abс" в "babcba". Читаем "bab", потом "cba", и не замечаем "babcba"

А вот если читать части с перекрытием, то строка будет найдена

Ищем "da" в "bcacdabcfa". Читаем "bcacd", потом "dabcf", потом остаток "fa", и во второй части находим "ab"


Вот смотрите - алгоритм двигает окно шириной P по массиву длиной T и выполняет проверки (начиная с правого конца, но это неважно). Таким образом, в каждый момент времени нужно иметь доступ к подмассиву длиной P. Для этого в первый момент времени можно прочитать часть файла длиной P, начиная с с позиции 0, потом прочитать такой же кусок, начиная с позиции i (сдвиг начала в Вашей реализации), потом со следующего значения i. Но чтение мелкими кусками невыгодно, поэтому читаете, например, 1 мегабайт в буфер text[] такой же длины и следите, когда i+j превысит эту величину. Как только превысит - читаете кусок с позиции readpos = 1048576 - P в text[] и продолжаете работу. Отличие только в том, что от индексов text[] отнимается readpos

2
  • Но мне же нужно вывести индексы строки, по которым проходится алгоритм, в правильном порядке. Если читать с перекрытием, то некоторые индексы будут проверятся несколько раз.
    – daniel
    31 окт 2020 в 12:30
  • Добавил в пост.
    – MBo
    31 окт 2020 в 14:53

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.