Поиск подстроки в строке - C (СИ) (79429)

Узнай цену своей работы

Формулировка задачи:

При запуске программы пользователь вводит две строки текста, каждая не длинее 1024 символа. Нужно вывести индексы всех вхождений второй строки в первую, используя алгоритм Бойера-Мура.
Программу я написал, но она не хочет работать, не могу отладить...
#include <stdio.h>
#include <string.h>
#define MAX 1023
 
int search_for_boyermoore(char first_line[MAX], char second_line[MAX]){
    int table_shift[256];
    int i;
    int j;
    int k;
    int length_of_the_first_line;
    int length_of_the_second_line;
 
    length_of_the_first_line = strlen(first_line);
    length_of_the_second_line = strlen(second_line);
 
    for (i=0; i<256; i++){
        table_shift[i] = length_of_the_first_line;
    }
    for (i=0; i<length_of_the_first_line-1; i++){
      table_shift[second_line[i]] = length_of_the_first_line-i-1;
    }
 
    for(i=length_of_the_first_line-1; i<length_of_the_second_line; i+=table_shift[first_line[i]]) {
        j = length_of_the_first_line-1; 
        k = i;   
        while ((j>=0)&&(second_line[j] == first_line[k])){
            k--;
            j--; 
        }
        if (j<0){
            return k+1;
        }
    }
    printf("%d", k);
    return -1;
}
 
int main (){
    char first_line[MAX];
    char second_line[MAX];
 
    printf("%s\n","Enter the first line...");
    scanf("%s/n", &first_line);
 
    printf("%s\n","Enter the second line");
    scanf("%s/n", &second_line);
 
    search_for_boyermoore(first_line[MAX], second_line[MAX]);
    return 0;
}
Visual Microsoft Studio выдает 8 предупреждений...

Решение задачи: «Поиск подстроки в строке»

textual
Листинг программы
#include <stdio.h>
#include <string.h>
#define MAX 1023
 
size_t search_for_boyermoore(char first_line[MAX], char second_line[MAX]){
    size_t table_shift[1023];
    size_t i;
    size_t j;
    size_t k;
    size_t length_of_the_first_line;
    size_t length_of_the_second_line;
 
    length_of_the_first_line = strlen(first_line);
    length_of_the_second_line = strlen(second_line);
 
    for (i=0; i<1023; i++){
        table_shift[i] = length_of_the_first_line;
    }
    for (i=0; i<length_of_the_first_line-1; i++){
      table_shift[(unsigned char)first_line[i]] = length_of_the_first_line-i-1;
    }
            
    for(i=length_of_the_first_line-1; i<length_of_the_second_line; i+=table_shift[second_line[i]]) {
        j = length_of_the_first_line-1;
        k = i;
        while ((j>=0)&&(first_line[j] == second_line[k])){
            k--;
            j--;
 
        }
        if (j<0){
            return k+1;
        }
 
    }
    printf("%d\n",k);
    return -1;
}
 
int main (){
    char first_line[MAX];
    char second_line[MAX];
 
    printf("%s\n","Enter the first line...");
    scanf("%s", &first_line);
 
    printf("%s\n","Enter the second line");
    scanf("%s", &second_line);
 
    search_for_boyermoore(first_line, second_line);
 
    return 0;
}

Объяснение кода листинга программы

В этом коде реализован алгоритм поиска подстроки с использованием таблицы смещений (Boyer-Moore). Список действий:

  1. Создаются две строки first_line и second_line, а также массив table_shift размером 1023.
  2. Определяются длины строк first_line и second_line с помощью функции strlen().
  3. Заполняется массив table_shift значением length_of_the_first_line.
  4. В цикле обрабатываются символы строки first_line: в массив table_shift записывается значение length_of_the_first_line - i - 1, где i - номер текущего символа в строке.
  5. В цикле выполняется поиск подстроки: начиная с последнего символа строки second_line, в каждой позиции проверяется, совпадает ли символ с символами строки first_line. Если символы совпадают, то сдвигается индекс в строке second_line на значение из массива table_shift. Если символы не совпадают, то продолжается поиск с предыдущей позиции. Если подстрока найдена, то возвращается ее индекс в строке second_line. Если подстрока не найдена, то возвращается -1.
  6. В основной функции main() запрашиваются строки first_line и second_line, затем вызывается функция search_for_boyermoore(), и результат выводится на экран.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 3.6 из 5
Похожие ответы