Нужно реализовать алгоритм Бойера-Мура с выводом индексов строки по которым он проходится (индексы считать от единицы).
Принцип алгоритма можно посмотреть здесь.
Пример:
подстрока: ДАННЫЕ
строка: ДАН ТЕКСТ В НЁМ ДАНЫ ДАННЫЕ
вывод программы: 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;
}
Подскажите как можно видоизменить мой код или просто подскажите подход который бы смог работать на больших данных.